Welcome to Subscribe On Youtube
920. Number of Music Playlists
Description
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
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ to be the number of playlists that can be made from $i$ songs with exactly $j$ different songs. We have $f[0][0] = 1$ and the answer is $f[goal][n]$.
For $f[i][j]$, we can choose a song that we have not listened before, so the previous state is $f[i  1][j  1]$, and there are $n  (j  1) = n  j + 1$ options. Thus, $f[i][j] += f[i  1][j  1] \times (n  j + 1)$. We can also choose a song that we have listened before, so the previous state is $f[i  1][j]$, and there are $j  k$ options. Thus, $f[i][j] += f[i  1][j] \times (j  k)$, where $j \geq k$.
Therefore, we have the transition equation:
\[f[i][j] = \begin{cases} 1 & i = 0, j = 0 \\ f[i  1][j  1] \times (n  j + 1) + f[i  1][j] \times (j  k) & i \geq 1, j \geq 1 \end{cases}\]The final answer is $f[goal][n]$.
The time complexity is $O(goal \times n)$, and the space complexity is $O(goal \times n)$. Here, $goal$ and $n$ are the parameters given in the problem.
Notice that $f[i][j]$ only depends on $f[i  1][j  1]$ and $f[i  1][j]$, so we can use rolling array to optimize the space complexity. The time complexity is unchanged.

class Solution { public int numMusicPlaylists(int n, int goal, int k) { final int mod = (int) 1e9 + 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]; } }

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]; } };

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]

func numMusicPlaylists(n int, goal int, k int) int { const mod = 1e9 + 7 f := make([][]int, goal+1) for i := range f { f[i] = make([]int, n+1) } f[0][0] = 1 for i := 1; i <= goal; i++ { for j := 1; j <= n; j++ { f[i][j] = f[i1][j1] * (n  j + 1) if j > k { f[i][j] += f[i1][j] * (j  k) } f[i][j] %= mod } } return f[goal][n] }

function numMusicPlaylists(n: number, goal: number, k: number): number { const mod = 1e9 + 7; const f = new Array(goal + 1).fill(0).map(() => new Array(n + 1).fill(0)); f[0][0] = 1; for (let i = 1; i <= goal; ++i) { for (let 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]; }

impl Solution { #[allow(dead_code)] pub fn num_music_playlists(n: i32, goal: i32, k: i32) > i32 { let mut dp: Vec<Vec<i64>> = vec![vec![0; n as usize + 1]; goal as usize + 1]; // Initialize the dp vector dp[0][0] = 1; // Begin the dp process for i in 1..=goal as usize { for j in 1..=n as usize { // Choose the song that has not been chosen before // We have n  (j  1) songs to choose dp[i][j] += dp[i  1][j  1] * ((n  ((j as i32)  1)) as i64); // Choose the song that has been chosen before // We have j  k songs to choose if j > k if (j as i32) > k { dp[i][j] += dp[i  1][j] * (((j as i32)  k) as i64); } // Update dp[i][j] dp[i][j] %= ((1e9 as i32) + 7) as i64; } } dp[goal as usize][n as usize] as i32 } }