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 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
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] × (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] × (j - k), where j ≥ k.
Therefore, we have the transition equation:
f[i][j] = \begin{cases}
1 & i = 0, j = 0 \
f[i - 1][j - 1] × (n - j + 1) + f[i - 1][j] × (j - k) & i ≥ 1, j ≥ 1
\end{cases}
The final answer is f[goal][n].
The time complexity is O(goal × n), and the space complexity is O(goal × n). Here, goal and n are the parameters given in the problem.
PythonJavaC++GoTypeScriptRust
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](code-box)
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];
}
}(code-box)
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];
}
};(code-box)
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[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]
}(code-box)
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];
}(code-box)
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
}
}(code-box)
Solution 2: Dynamic Programming (Space Optimization)
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).
PythonJavaC++GoTypeScript
class Solution:
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
mod = 10**9 + 7
f = [0] * (goal + 1)
f[0] = 1
for i in range(1, goal + 1):
g = [0] * (goal + 1)
for j in range(1, n + 1):
g[j] = f[j - 1] * (n - j + 1)
if j > k:
g[j] += f[j] * (j - k)
g[j] %= mod
f = g
return f[n](code-box)
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
final int mod = (int) 1e9 + 7;
long[] f = new long[n + 1];
f[0] = 1;
for (int i = 1; i <= goal; ++i) {
long[] g = new long[n + 1];
for (int j = 1; j <= n; ++j) {
g[j] = f[j - 1] * (n - j + 1);
if (j > k) {
g[j] += f[j] * (j - k);
}
g[j] %= mod;
}
f = g;
}
return (int) f[n];
}
}(code-box)
class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
const int mod = 1e9 + 7;
vector<long long> f(n + 1);
f[0] = 1;
for (int i = 1; i <= goal; ++i) {
vector<long long> g(n + 1);
for (int j = 1; j <= n; ++j) {
g[j] = f[j - 1] * (n - j + 1);
if (j > k) {
g[j] += f[j] * (j - k);
}
g[j] %= mod;
}
f = move(g);
}
return f[n];
}
};(code-box)
func numMusicPlaylists(n int, goal int, k int) int {
const mod = 1e9 + 7
f := make([]int, goal+1)
f[0] = 1
for i := 1; i <= goal; i++ {
g := make([]int, goal+1)
for j := 1; j <= n; j++ {
g[j] = f[j-1] * (n - j + 1)
if j > k {
g[j] += f[j] * (j - k)
}
g[j] %= mod
}
f = g
}
return f[n]
}(code-box)
function numMusicPlaylists(n: number, goal: number, k: number): number {
const mod = 1e9 + 7;
let f = new Array(goal + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= goal; ++i) {
const g = new Array(goal + 1).fill(0);
for (let j = 1; j <= n; ++j) {
g[j] = f[j - 1] * (n - j + 1);
if (j > k) {
g[j] += f[j] * (j - k);
}
g[j] %= mod;
}
f = g;
}
return f[n];
}(code-box)
