(Python3) - LeetCode (Medium) : 2466. Count Ways To Build Good Strings

https://leetcode.com/problems/count-ways-to-build-good-strings

 

dp 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

MOD를 선언 후 10**9 + 7로 초기화합니다.

📔 풀이과정

어떤 문자열 i길이를 만들기 위해 0을 zero개와 1을 one개를 사용할 때 다음과 같은 점화식을 세울 수 있습니다.

$${D[i] = D[i-one] + D[i-zero]}$$

 

1. 빈 문자열을 만드는 경우는 1이므로 dp[0]은 1로 초기화하고 1에서 high까지 for loop또는 재귀함수를 수행하며 각자 길이를 만드는 경우의 수를 구해줍니다.

 

2. low에서 high까지 다시 dp 값을 answer에 누적해 더해준 후 MOD연산을 적용해 갱신합니다.

📔 정답 출력 | 반환

answer 또는 재귀함수 결과를 반환합니다.

---

📕 Code

📔 Python3 (bottom up)

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        MOD = 10**9 + 7
  
        answer = 0

        dp = [0] * (high+1)
        dp[0] = 1

        for i in range(1, high + 1):
            if i - zero >= 0:
                dp[i] += dp[i-zero]
            if i - one >= 0:
                dp[i] += dp[i-one]
            dp[i] %= MOD
        for i in range(low, high + 1):
            answer = (answer+dp[i]) % MOD
            
        return answer

📔 Python3 (top down)

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        MOD = 10**9 + 7
		memo = {}
        def dp(length):
            if length > high:
                return 0
            if length in memo:
                return memo[length]
            count = 1 if length >= low else 0
            count += dp(length+one)
            count += dp(length+zero)
            count %= MOD

            memo[length] = count
            return count
        return dp(0)

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.