920. Number of Music Playlists - Explanation

1. Dynamic Programming (Top-Down)

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        dp = {}

        def count(cur_goal, old_songs):
            if cur_goal == 0 and old_songs == n:
                return 1
            if cur_goal == 0 or old_songs > n:
                return 0
            if (cur_goal, old_songs) in dp:
                return dp[(cur_goal, old_songs)]

            res = (n - old_songs) * count(cur_goal - 1, old_songs + 1)
            if old_songs > k:
                res += (old_songs - k) * count(cur_goal - 1, old_songs)
            dp[(cur_goal, old_songs)] = res % mod
            return dp[(cur_goal, old_songs)]

        return count(goal, 0)

Time & Space Complexity

Time complexity: $O(g * n)$
Space complexity: $O(g * n)$

Where $g$ is the number of songs to listen and $n$ is the number of different songs.

2. Dynamic Programming (Bottom-Up)

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 cur_goal in range(1, goal + 1):
            for old_songs in range(1, n + 1):
                res = (dp[cur_goal - 1][old_songs - 1] * (n - old_songs + 1)) % mod
                if old_songs > k:
                    res = (res + dp[cur_goal - 1][old_songs] * (old_songs - k)) % mod
                dp[cur_goal][old_songs] = res

        return dp[goal][n]

Time & Space Complexity

Time complexity: $O(g * n)$
Space complexity: $O(g * n)$

Where $g$ is the number of songs to listen and $n$ is the number of different songs.

3. Dynamic Programming (Space Optimized)

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        dp = [0] * (n + 1)

        for cur_goal in range(1, goal + 1):
            prev = 1 if cur_goal == 1 else 0
            for old_songs in range(1, n + 1):
                res = (prev * (n - old_songs + 1)) % mod
                if old_songs > k:
                    res = (res + dp[old_songs] * (old_songs - k)) % mod
                prev = dp[old_songs]
                dp[old_songs] = res

        return dp[n]

Time & Space Complexity

Time complexity: $O(g * n)$
Space complexity: $O(n)$

Where $g$ is the number of songs to listen and $n$ is the number of different songs.