Dynamic Programming: Finding The Recurrence Relation

 

276. Paint Fence

https://leetcode.com/problems/paint-fence/

Paint Fence - LeetCode

let dp[i] be # of all ways painting i-th fence:

then, dp[i] = num_same(i) + num_diff(i) holds.

(where num_same(i) = painting i-th fence with the same color of i-1-th fence, num_diff(i) with a different color from it)

num_diff(i) = dp[i-1] * (k-1)

num_same(i) = num_diff(i-1) = dp[i-2] * (k-1)

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 1:
            return k
        dp = [0] * n
        dp[0] = k
        dp[1] = k ** 2
        for i in range(2, n):
            dp[i] = (dp[i-2] + dp[i-1])*(k-1)
        return dp[-1]

 

920. Number of Music Playlists

https://leetcode.com/problems/number-of-music-playlists/description/

Number of Music Playlists - LeetCode

Let dp[i, j] = # all ways with i playlist with j different songs

1) adding a new song: dp[i-1, j-1] * (n - j + 1)

2) adding an old song w/o the constraint: dp[i-1, j] * j 

3) adding an old song with the constraint: dp[i-1, j] * (j - k) only if j > k

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10 ** 9 + 7
        dp = [[0] * (n+1) for _ in range(goal+1)]
        dp[0][0] = 1
        for i in range(1, goal+1):
            for j in range(1, n+1):
                dp[i][j] = dp[i-1][j-1] * (n - j + 1)
                if j > k:
                    dp[i][j] += dp[i-1][j] * (j - k)
                dp[i][j] %= mod
        return dp[-1][-1]

        # top-down approach
        # @lru_cache()
        # def dp(i, j):
        #     if i == 0:
        #         return j == 0
        #     ret = dp(i-1, j-1) * (n-j+1)
        #     ret += dp(i-1, j) * max(j-k, 0)
        #     return ret % (10**9+7)
        # return dp(goal, n)