BinarySearch 0759 Playlist Count

Problem statement

https://binarysearch.com/problems/Playlist-Count/

Solution

Equal to Leetcode 0920 Number of Music Playlists

Complexity

Time and space complexity of this solution is O(NL).

Code

class Solution:
    def numMusicPlaylists(self, N, L, K):
        
        @lru_cache(None)
        def dp(i, j):
            if i == 0: return j == 0
            ans = dp(i-1, j-1) * (N-j+1)
            ans += dp(i-1, j) * max(j-K, 0)
            return ans % (10**9+7)

        return dp(L, N)