⚡Flashcard Drill➔
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

  1. Let dp[i][j] be the number of playlists of length i that use exactly j distinct songs.
  2. Adding a new song has n - j + 1 choices, giving dp[i-1][j-1] * (n - j + 1).
  3. Repeating an existing song is allowed only for the j - k songs that are outside the cooldown window, giving dp[i-1][j] * max(j - k, 0).
  4. The answer is dp[goal][n], since all n songs 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 last k distinct songs are still in the cooldown window.
  • Using j instead of j - k in 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 all n songs, so the answer is dp[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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems