Number of Music Playlists

How it works

Looking at the bottom-up recurrence, each row only depends on the previous row. This means we do not need to store the entire 2D table. Instead, we can use a single 1D array and update it in place, being careful to preserve the previous row's values where needed. This reduces space from O(goal * n) to O(n).

Steps

1. Create a 1D array dp[n+1] initialized to 0.
2. For each playlist length cur_goal from 1 to goal:
   • Track prev to store the value from the previous row that we need before overwriting.
   • Initialize prev = 1 when cur_goal == 1 (base case for adding the first song), otherwise prev = 0.
   • For each count of distinct songs old_songs from 1 to n:
     • Compute the new value using prev (for adding a new song) and dp[old_songs] (for replaying an old song).
     • Update prev to the old value of dp[old_songs] before overwriting.
     • Store the result in dp[old_songs].
3. Return dp[n].

Complexity

• Time complexity: O(g * n)
• Space complexity: O(n)

Where g is the number of songs to listen and n is the number of different songs.

Things to watch for

Forgetting the Gap Constraint for Replaying Songs

A song can only be replayed after k other songs have been played. This means with old_songs distinct songs used, only old_songs - k are eligible for replay (if old_songs > k). Forgetting this constraint or using old_songs directly leads to overcounting.

Integer Overflow in Modular Arithmetic

Multiplying two values before taking the modulo can overflow 32-bit integers. Always cast to long or long long before multiplication, then apply modulo. For example, (n - oldSongs) * count can overflow if not handled properly.

Incorrect Base Case Definition

The base case should be dp[0][0] = 1 (one way to have an empty playlist with zero songs used). Setting dp[0][n] = 1 or other incorrect initializations will propagate errors through all subsequent states.

Confusing State Dimensions

The DP state tracks (playlist_length, distinct_songs_used). Confusing which dimension is which, or iterating in the wrong order, leads to accessing uncomputed states or incorrect transitions. In bottom-up, iterate playlist length in the outer loop and distinct songs in the inner loop.

Not Requiring Exactly N Distinct Songs

The final answer must use exactly n distinct songs. A common error is returning dp[goal][any] summed over all possible song counts, when it should specifically be dp[goal][n].

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        dp = [0] * (n + 1)

        for cur_goal in range(1, goal + 1):
            prev = 1 if cur_goal == 1 else 0
            for old_songs in range(1, n + 1):
                res = (prev * (n - old_songs + 1)) % mod
                if old_songs > k:
                    res = (res + dp[old_songs] * (old_songs - k)) % mod
                prev = dp[old_songs]
                dp[old_songs] = res

        return dp[n]

class Solution {
private:
    static const int MOD = 1e9 + 7;

public:
    int numMusicPlaylists(int n, int goal, int k) {
        vector<int> dp(n + 1);

        for (int curGoal = 1; curGoal <= goal; curGoal++) {
            int prev = curGoal == 1 ? 1: 0;
            for (int oldSongs = 1; oldSongs <= n; oldSongs++) {
                int res = (long long) prev * (n - oldSongs + 1) % MOD;
                if (oldSongs > k) {
                    res = (res + (long long) dp[oldSongs] * (oldSongs - k) % MOD) % MOD;
                }
                prev = dp[oldSongs];
                dp[oldSongs] = res;
            }
        }

        return dp[n];
    }
};