Number of Music Playlists: DP with Replay Constraints

LeetCode Number of Music Playlists (problem 920) asks you to count how many valid playlists you can build given some replay constraints. You have n different songs and need to create a playlist of length goal. Every song must appear at least once, and a song can only be replayed after k other songs have been played since its last appearance. Return the count modulo 10^9 + 7.

The problem

Given integers n, goal, and k:

• The playlist has goal songs total
• Every one of n songs must appear at least once
• A song can only be replayed if at least k other songs have been played between occurrences

Return the number of possible playlists, modulo 10^9 + 7.

The brute force approach

You could try to enumerate all sequences of length goal from n songs, then filter to those where every song appears and the replay constraint holds. But with goal up to 100 and n up to 100, the number of raw sequences is astronomical. Even with backtracking, the branching factor is too large to explore directly.

The key observation is that this is a counting problem with overlapping subproblems. At each position in the playlist, your choice depends on how many unique songs you have used so far and what the replay rule allows. That structure points directly at dynamic programming.

The key insight

Define dp[i][j] as the number of valid playlists of length i that contain exactly j unique songs. At each position, you have two choices:

1. Add a new song. If you have used j-1 unique songs so far, you can pick any of the n - (j-1) remaining songs. This gives: dp[i-1][j-1] * (n - j + 1).

2. Replay an old song. If you already have j unique songs in a playlist of length i-1, you can replay one that is not in the last k positions. The number of eligible songs is max(j - k, 0). This gives: dp[i-1][j] * max(j - k, 0).

The base case is dp[0][0] = 1 (an empty playlist with zero songs is trivially valid). The answer is dp[goal][n], since you need all n songs to appear.

Step-by-step walkthrough

Let's trace through a small example with n=2, goal=3, k=0. Since k=0, any song can be replayed immediately (no gap required).

The code

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 i in range(1, goal + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
            dp[i][j] += dp[i-1][j] * max(j - k, 0) % MOD
            dp[i][j] %= MOD
    return dp[goal][n]

The outer loop iterates over playlist positions from 1 to goal. The inner loop iterates over the number of unique songs from 1 to n. For each cell, you combine the "add new" and "replay old" transitions. The modulo operation keeps values from overflowing.

Complexity analysis

With goal and n both at most 100, the 2D table has at most 10,000 cells. Each cell is computed in O(1), making the total work trivial for any modern machine. The space-optimized version uses a single array of length n + 1 and alternates between two rows.

The building blocks

Counting with constrained transitions

The core pattern here is a DP where transitions depend on what has already been used. You see this same structure in Decode Ways, where valid decodings depend on whether the current digit pair forms a valid letter. The playlist problem adds a "cooldown" flavor through the k parameter.

Combinatorial DP with modular arithmetic

Since the answer can be enormous, you work modulo 10^9 + 7 throughout. This is standard for counting problems on LeetCode. The key rule: apply % MOD after every multiplication and addition to prevent overflow. Python handles big integers natively, but the modulo keeps you in the habit for languages that do not.

The "must use all" constraint

The requirement that every song appears at least once is what makes dp[goal][n] the answer rather than summing over all j. This "must cover all items" constraint also appears in problems like Combination Sum IV, where you need specific targets, and in set-cover style counting problems.

Edge cases

• n equals goal with k equals n-1. Every song plays exactly once, and the replay rule never triggers. The answer is n! (all permutations).
• k equals 0. Songs can be replayed immediately. This maximizes the count since there are no cooldown restrictions.
• n equals 1 and goal equals 1 and k equals 0. Only one playlist: the single song. The DP correctly gives dp[1][1] = 1.
• goal equals n. You must play each song exactly once (no room for replays). The answer is n! regardless of k, since every position introduces a new song.
• Large k close to n. When k is close to n, replay becomes very restricted. You might be forced to keep introducing new songs for a long time before any replay is possible.

From understanding to recall

The tricky part of this problem is not the code. It is remembering the state definition and the two transitions. When you review this problem, focus on these questions:

• What do i and j represent? (Playlist length and number of unique songs used.)
• Why is "add new" multiplied by n - j + 1? (That is how many songs you have not yet used.)
• Why is "replay" multiplied by max(j - k, 0)? (Only songs outside the last k positions are eligible.)

Practice writing the recurrence from scratch. Once you can derive dp[i][j] = dp[i-1][j-1] * (n-j+1) + dp[i-1][j] * max(j-k, 0) without looking, you own this problem. The code follows mechanically from the recurrence.

Related posts

• Climbing Stairs - The simplest DP counting problem that builds intuition for state transitions
• Decode Ways - Another counting DP where constraints limit which transitions are valid
• Combination Sum IV - Counting arrangements with repetition constraints similar to the playlist rule