Leetcode: 920. Number of Music Playlists

Problem Statement

• Mistake: Did not consider different approaches. Got stuck on a recursion using \((i, r)\) the \(i\) song to play having to play \(r\) required songs.
• Can we break-down the problem in small and easily to solve parts? Suppose that you played \(i\) songs which \(j\) are unique songs. There are two ways to select the next song: (1) you play one of \(n - j\) new songs, or (2) you play one \(\max(j - k, 0)\) already played songs. Time and space complexity is \(O(g \times n)\).

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

        @cache
        def dfs(i, u):
            if i == goal:
                return 1 if u == n else 0
            return ((n - u) * dfs(i + 1, u + 1) + max(u - k, 0) * dfs(i + 1, u)) % MOD

        return dfs(0, 0)