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 modulo109 + 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$.
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.
implSolution{#[allow(dead_code)]pubfnnum_music_playlists(n:i32,goal:i32,k:i32)->i32{letmutdp:Vec<Vec<i64>>=vec![vec![0;nasusize+1];goalasusize+1];// Initialize the dp vectordp[0][0]=1;// Begin the dp processforiin1..=goalasusize{forjin1..=nasusize{// Choose the song that has not been chosen before// We have n - (j - 1) songs to choosedp[i][j]+=dp[i-1][j-1]*((n-((jasi32)-1))asi64);// Choose the song that has been chosen before// We have j - k songs to choose if j > kif(jasi32)>k{dp[i][j]+=dp[i-1][j]*(((jasi32)-k)asi64);}// Update dp[i][j]dp[i][j]%=((1e9asi32)+7)asi64;}}dp[goalasusize][nasusize]asi32}}
We notice that $f[i][j]$ is only related to $f[i - 1][j - 1]$ and $f[i - 1][j]$. Therefore, we can use a rolling array to optimize the space complexity, reducing the space complexity to $O(n)$.