Number of Music Playlists Python Solution

lcpy gen -n 920   # by problem number
lcpy gen -s number_of_music_playlists   # by problem name

Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].

Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

class Solution:
    # Time: O(goal * n)
    # Space: O(n)
    def num_music_playlists(self, n: int, goal: int, k: int) -> int:
        mod = 1_000_000_007
        # dp[j] = number of playlists of current length with j unique songs
        dp = [0] * (n + 1)
        dp[0] = 1
        for _ in range(goal):
            new_dp = [0] * (n + 1)
            for j in range(1, n + 1):
                # Play a new song: choose 1 of the (n - (j - 1)) unused songs
                new_dp[j] = dp[j - 1] * (n - j + 1) % mod
                # Replay a song: any of the j - k previously played songs
                # (a song is replayable once k other songs have been played)
                if j > k:
                    new_dp[j] = (new_dp[j] + dp[j] * (j - k)) % mod
            dp = new_dp
        return dp[n]