920. Number of Music Playlists

Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:

• Every song is played at least once.
  -A song can only be played again only if k other songs have been played.

Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo $10^9+7$.
 

Example 1:

Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

Example 2:

Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].

Example 3:

Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

Constraints:

• 0 <= k < n <= goal <= 100

From: LeetCode
Link: 920. Number of Music Playlists

Solution:

Ideas:

• State definition:
  dp[i][j] = number of playlists of length i that contain exactly j unique songs.

• Transition:

  1. Add a new unique song:
     Choose one of the remaining (n - (j - 1)) songs that haven’t appeared yet →
     dp[i-1][j-1] * (n - (j - 1))

  2. Replay an old song:
     Choose one of the already used (j - k) songs that are allowed to repeat →
     dp[i-1][j] * (j - k)

• Base case:
  dp[0][0] = 1 (empty playlist, 0 unique songs).

• Answer:
  dp[goal][n] → playlists of length goal containing all n unique songs.

Code:

#define MOD 1000000007

int numMusicPlaylists(int n, int goal, int k) {
    long dp[101][101] = {0}; // dp[i][j]: playlists of length i with j unique songs
    dp[0][0] = 1;

    for (int i = 1; i <= goal; i++) {
        for (int j = 1; j <= n; j++) {
            // Case 1: Add a new unique song
            dp[i][j] = (dp[i - 1][j - 1] * (n - (j - 1))) % MOD;

            // Case 2: Replay an old song (only if more than k unique songs are already played)
            if (j > k)
                dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD;
        }
    }

    return (int)dp[goal][n];
}