NeetCode #746LC-920Hard2-D Dynamic Programming
← Back to All Problems#746 · #920 · Number of Music Playlists(播放列表的数量)
📌 Problem Statement & Constraints
You build a playlist of length
goal from n distinct songs. Every song must be played at least once, and a song may repeat only if at least k other songs have been played since its last occurrence. Return the number of playlists modulo 1e9+7. Constraints: 0 <= k < n <= 100, 1 <= goal <= 100.💡 Core Algorithmic Approaches
- Let
dp[i][j]be the number of playlists of lengthithat use exactlyjdistinct songs. - Adding a new song has
n - j + 1choices, givingdp[i-1][j-1] * (n - j + 1). - Repeating an existing song is allowed only for the
j - ksongs that are outside the cooldown window, givingdp[i-1][j] * max(j - k, 0). - The answer is
dp[goal][n], since allnsongs must be used.
💻 Benchmark Python3 Implementation
class Solution:
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
MOD = 10**9 + 7
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, goal + 1):
nxt = [0] * (n + 1)
for j in range(1, min(i, n) + 1):
# introduce a brand-new song: (n - j + 1) choices
nxt[j] = dp[j - 1] * (n - j + 1) % MOD
# replay one of the j used songs, excluding the last k played
nxt[j] = (nxt[j] + dp[j] * max(j - k, 0)) % MOD
dp = nxt
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(goal * n): one state per (length, distinct count) pair.
💾 Space Complexity
O(n): one rolling array.
⚠️ Interview Pitfalls & Follow-ups
- Allowing any repeat: the
max(j - k, 0)factor encodes that the lastkdistinct songs are still in the cooldown window. - Using
jinstead ofj - kin the repeat term: the songs inside the window must be excluded, otherwise the playlist violates the rule. - Answering
dp[goal][goal]: the playlist must use allnsongs, so the answer isdp[goal][n]. - Forgetting the modulo: the counts are astronomically large.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.