# Number of Music Playlists
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-music-playlists)
Canonical: https://scaleengineer.com/dsa/problems/number-of-music-playlists
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Companies:** [Coursera](https://scaleengineer.com/companies/coursera)
---
## Problem
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** `109 + 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`

# Approaches
## Recursion with Memoization (Top-Down DP)
This approach solves the problem using recursion with memoization, which is a top-down dynamic programming technique. We define a function `solve(i, j)` that calculates the number of playlists of length `i` containing exactly `j` unique songs. To avoid recomputing results for the same state `(i, j)`, we store them in a 2D memoization table.
**Time:** O(goal * n) - Each state `(i, j)` is computed only once due to memoization. There are `goal * n` possible states. · **Space:** O(goal * n) - This is for the memoization table. The recursion depth can also go up to `goal`, contributing to the call stack space.
**Pros:** The logic directly translates the recurrence relation, making it intuitive to understand.; It only computes states that are reachable from the initial call, which can be more efficient if the state space is sparse.
**Cons:** May lead to a `StackOverflowError` for very large `goal` values, though not an issue with the given constraints.; Generally has slightly more overhead than the iterative (tabulation) approach due to recursive function calls.
### Explanation
The core idea is to build the playlist song by song and keep track of its length (`i`) and the number of unique songs used (`j`). When we want to determine the number of playlists for state `(i, j)`, we consider the `i`-th song we are adding.

There are two possibilities for this song:

1.  **It's a new, unique song.** For this to happen, the first `i-1` songs must have formed a playlist with `j-1` unique songs. We can then pick any of the `n - (j-1)` songs that haven't been used yet. The number of ways for this case is `solve(i - 1, j - 1) * (n - j + 1)`.

2.  **It's a repetition of a song already in the playlist.** For this, the first `i-1` songs must have already contained `j` unique songs. The constraint is that a song can be replayed only if `k` other songs have been played since its last appearance. With `j` unique songs available, we can choose any of them to repeat, except for the `k` most recent unique songs played. This gives us `j - k` choices for the song to repeat. This is only possible if `j > k`. The number of ways for this case is `solve(i - 1, j) * (j - k)`.

The total number of ways for `solve(i, j)` is the sum of these two cases. We use a `memo` table to store and retrieve previously computed results, preventing redundant calculations.

```java
class Solution {
    long[][] memo;
    int N, K;
    long MOD = 1_000_000_007;

    public int numMusicPlaylists(int n, int goal, int k) {
        this.N = n;
        this.K = k;
        this.memo = new long[goal + 1][n + 1];
        for (long[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return (int) solve(goal, n);
    }

    private long solve(int i, int j) {
        // A playlist of length i with j unique songs
        if (i == 0 && j == 0) {
            return 1;
        }
        if (i == 0 || j == 0) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        // Case 1: The last song is a new song.
        // We had a playlist of length i-1 with j-1 unique songs.
        // We choose one of the (N - (j-1)) new songs.
        long res = solve(i - 1, j - 1) * (N - j + 1);
        res %= MOD;

        // Case 2: The last song is a repetition of an existing song.
        // We had a playlist of length i-1 with j unique songs.
        // We can repeat a song if j > K. The number of songs we can choose from is (j - K).
        if (j > K) {
            res += solve(i - 1, j) * (j - K);
            res %= MOD;
        }

        return memo[i][j] = res;
    }
}
```
### Algorithm
1.  Define a recursive function `solve(i, j)` that computes the number of playlists of length `i` with `j` unique songs.
2.  Use a 2D array `memo` of size `(goal + 1) x (n + 1)` for memoization, initialized with a sentinel value (e.g., -1).
3.  Implement the base cases for the recursion:
    *   If `i == 0` and `j == 0`, return 1 (one way to have an empty playlist).
    *   If `i == 0` or `j == 0`, return 0 (it's impossible to form a playlist under these conditions).
    *   Also, if `j > n` or `j > i`, it's an invalid state, so return 0.
4.  In the `solve(i, j)` function, first check if the result is already in `memo`. If so, return it.
5.  Otherwise, compute the result using the recurrence relation:
    *   **Case 1 (New Song):** The last song is a new one. This is possible if we had a playlist of length `i-1` with `j-1` unique songs. There are `n - (j-1)` choices for this new song. The number of ways is `solve(i - 1, j - 1) * (n - j + 1)`.
    *   **Case 2 (Repeated Song):** The last song is a repeat. This is possible if we had a playlist of length `i-1` with `j` unique songs. The number of available songs to repeat is `max(0, j - k)`. The number of ways is `solve(i - 1, j) * (j - k)` (only if `j > k`).
6.  Sum the results from both cases (modulo `10^9 + 7`), store it in `memo[i][j]`, and return it.
7.  The initial call to start the process is `solve(goal, n)`.

## 2D Dynamic Programming (Tabulation)
This approach uses bottom-up dynamic programming, also known as tabulation. We build the solution iteratively by filling a 2D table `dp[i][j]`, where `i` represents the playlist length and `j` represents the number of unique songs. We start from the base case (an empty playlist) and compute the values for larger playlists based on the results of smaller ones.
**Time:** O(goal * n) - We iterate through a `goal x n` grid to fill the DP table. · **Space:** O(goal * n) - For the 2D DP table.
**Pros:** Avoids recursion overhead and the risk of stack overflow, making it slightly faster and more robust than the recursive approach.; The iterative nature of filling the table is often straightforward to implement and debug.
**Cons:** Requires `O(goal * n)` space, which is less optimal than the space-optimized version, although acceptable for the given constraints.
### Explanation
We define `dp[i][j]` as the number of possible playlists of length `i` that contain exactly `j` unique songs. Our goal is to find `dp[goal][n]`. We build this table starting from `dp[0][0] = 1`.

For each cell `dp[i][j]`, we consider how it could have been formed by adding the `i`-th song:

1.  **The `i`-th song is a new song:** We must have started with a playlist of length `i-1` with `j-1` unique songs. There are `dp[i-1][j-1]` such playlists. We can choose any of the `n - (j-1)` songs not yet used. So, this contributes `dp[i-1][j-1] * (n - j + 1)` to `dp[i][j]`.

2.  **The `i`-th song is a repeated song:** We must have started with a playlist of length `i-1` with `j` unique songs. There are `dp[i-1][j]` such playlists. We can repeat any of the `j` songs, but to satisfy the constraint, we cannot repeat a song that was played too recently. The number of available songs to repeat is `j - k`. This is only possible if `j > k`. This contributes `dp[i-1][j] * (j - k)` to `dp[i][j]`.

The recurrence relation is:
`dp[i][j] = (dp[i-1][j-1] * (n - j + 1)) + (dp[i-1][j] * max(0, j - k))`

We fill the table row by row, and the final answer is `dp[goal][n]`.

```java
class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        long MOD = 1_000_000_007;
        long[][] dp = new long[goal + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                // Case 1: Add a new song
                // Comes from a playlist of length i-1 with j-1 unique songs.
                dp[i][j] += dp[i - 1][j - 1] * (n - j + 1);
                dp[i][j] %= MOD;

                // Case 2: Replay an existing song
                // Comes from a playlist of length i-1 with j unique songs.
                if (j > k) {
                    dp[i][j] += dp[i - 1][j] * (j - k);
                    dp[i][j] %= MOD;
                }
            }
        }

        return (int) dp[goal][n];
    }
}
```
### Algorithm
1.  Create a 2D DP table `dp` of size `(goal + 1) x (n + 1)` to store the number of playlists. `dp[i][j]` will store the number of playlists of length `i` with `j` unique songs.
2.  Initialize the base case: `dp[0][0] = 1`, representing one empty playlist of length 0 with 0 unique songs.
3.  Iterate through playlist lengths `i` from 1 to `goal`.
4.  For each `i`, iterate through the number of unique songs `j` from 1 to `n` (and `j <= i`).
5.  Calculate `dp[i][j]` using the values from the previous row (`i-1`):
    *   **Add a new song:** `dp[i-1][j-1] * (n - j + 1)`. This term represents taking a playlist of length `i-1` with `j-1` unique songs and adding one of the `n-(j-1)` unused songs.
    *   **Replay an existing song:** `dp[i-1][j] * (j - k)`. This term represents taking a playlist of length `i-1` with `j` unique songs and replaying one of the `j-k` songs that are not restricted by the `k` constraint. This is only added if `j > k`.
6.  Sum these two terms (modulo `10^9 + 7`) to get `dp[i][j]`.
7.  The final answer is the value in `dp[goal][n]`.

## Space-Optimized 1D Dynamic Programming
This approach optimizes the 2D DP solution by reducing its space complexity. We observe that to compute the values for the current playlist length `i`, we only need the results from the previous length `i-1`. This allows us to use only a 1D array to store the DP states, bringing the space complexity down from `O(goal * n)` to `O(n)`.
**Time:** O(goal * n) - The number of computations remains the same as the 2D DP approach. · **Space:** O(n) - We only need a single 1D array of size `n+1` to store the DP states.
**Pros:** Highly space-efficient, using only `O(n)` space.; Maintains the optimal time complexity of `O(goal * n)`.
**Cons:** The logic, especially with the single-array optimization and backward iteration, can be less intuitive to grasp compared to the 2D DP approach.
### Explanation
Instead of a full 2D table, we use a single 1D array, `dp`, of size `n+1`. `dp[j]` will store the number of playlists for the current length `i` with `j` unique songs. 

As we iterate from `i = 1` to `goal`, we update this `dp` array. The key challenge is that the update rule for `dp[j]` depends on both `dp[j]` and `dp[j-1]` from the *previous* iteration. If we update in-place with a forward `j` loop, `dp[j-1]` would be overwritten before it's used to calculate `dp[j]`. 

To solve this, we iterate `j` from `n` down to 1. When we compute the new `dp[j]`, the values `dp[j]` and `dp[j-1]` on the right-hand side of the equation are still the values from the previous `i` iteration, which is exactly what we need.

Another subtlety is handling `dp[0]`. `dp[0]` is initially 1 (for `i=0, j=0`). However, for any `i > 0`, `dp[i][0]` should be 0. We must manually set `dp[0] = 0` after the first iteration to ensure correct calculations for subsequent steps.

```java
class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        long MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= goal; i++) {
            // Iterate j backwards to use dp array from the previous state (i-1).
            for (int j = n; j >= 1; j--) {
                // Case 1: Add a new song
                long term1 = dp[j - 1] * (n - j + 1);
                
                // Case 2: Replay an existing song
                long term2 = 0;
                if (j > k) {
                    term2 = dp[j] * (j - k);
                }
                
                dp[j] = (term1 + term2) % MOD;
            }
            // For any playlist of length i > 0, it's impossible to have 0 unique songs.
            // This sets up dp[0] for the next iteration's calculation of dp[1].
            dp[0] = 0;
        }

        return (int) dp[n];
    }
}
```
### Algorithm
1.  Initialize a 1D array `dp` of size `n + 1`. `dp[j]` will store the number of playlists of the current length with `j` unique songs.
2.  Set the base case: `dp[0] = 1` for a playlist of length 0.
3.  Iterate `i` from 1 to `goal` (for playlist length).
4.  Inside this loop, iterate `j` from `n` down to 1. A backward loop is crucial to ensure that when we calculate `dp[j]`, we are using `dp[j]` and `dp[j-1]` from the previous iteration (`i-1`).
5.  Update `dp[j]` using the same recurrence relation:
    `dp[j] = (dp[j-1] * (n - j + 1)) + (dp[j] * (j - k))` (if `j > k`).
6.  After the inner `j` loop finishes for a given `i`, we must set `dp[0] = 0`. This is because for any playlist of length `i > 0`, it's impossible to have 0 unique songs. This correctly sets up `dp[0]` for the next iteration's calculation of `dp[1]`.
7.  After the outer loop completes, `dp[n]` will hold the number of playlists of length `goal` with `n` unique songs.

# Solutions
### Java

```java
class Solution {
public
  int numMusicPlaylists(int n, int goal, int k) {
    final int mod = (int)1 e9 + 7;
    long[][] f = new long[goal + 1][n + 1];
    f[0][0] = 1;
    for (int i = 1; i <= goal; ++i) {
      for (int j = 1; j <= n; ++j) {
        f[i][j] = f[i - 1][j - 1] * (n - j + 1);
        if (j > k) {
          f[i][j] += f[i - 1][j] * (j - k);
        }
        f[i][j] %= mod;
      }
    }
    return (int)f[goal][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numMusicPlaylists(int n, int goal, int k) {
    const int mod = 1e9 + 7;
    long long f[goal + 1][n + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= goal; ++i) {
      for (int j = 1; j <= n; ++j) {
        f[i][j] = f[i - 1][j - 1] * (n - j + 1);
        if (j > k) {
          f[i][j] += f[i - 1][j] * (j - k);
        }
        f[i][j] %= mod;
      }
    }
    return f[goal][n];
  }
};

```

### Python

```python
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int: mod = 10 ** 9 + 7 f = [[0] * (n + 1) for _ in range(goal + 1)] f[0][0] = 1 for i in range(1, goal + 1): for j in range(1, n + 1): f[i][j] = f[i - 1][j - 1] * (n - j + 1) if j > k: f[i][j] += f[i - 1][j] * (j - k) f[i][j] %= mod return f[goal][n]

```