Your music player contains N different songs and she wants to listen to L(not necessarily different) songs during your trip. You 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
Return the number of possible playlists. As the answer can be very large, return it modulo 10^9 + 7.
Example 1:
Input: N = 3, L = 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], [3, 2, 1].
Example 2:
Input: N = 2, L = 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], [1, 2, 2]
Example 3:
Input: N = 2, L = 3, K = 1
Output: 2
Explanation: There are 2 possible playlists. [1, 2, 1], [2, 1, 2]
Note:
0 <= K < N <= L <= 100
class Solution {
public int numMusicPlaylists(int N, int L, int K) {
int mod = 1_000_000_007;
// dp[i][j] => Number of playlists, if we want to listen to i songs & we have j
// distinct songs (j<=i)
long[][] dp = new long[L + 1][N + 1];
// Only 1 playlist possible if we don't want to listen to any song
dp[0][0] = 1;
for (int i = 1; i <= L; i++) {
// By loop from 1->i, we are making sure that j<=i is maintained
for (int j = 1; j <= i && j <= N; j++) {
// If we choose a new Song to listen to
// We can choose from the remaining N - (j - 1) songs
dp[i][j] = (dp[i - 1][j - 1] * (N - (j - 1))) % mod;
// If we choose an old song,
// then we need to make sure that k distinct songs have been already played
// dp[i-1][j] * (j-K) -> Out of the 'j' distinct songs, we are choosing from
// j-K, because we want k different songs to be played before this song
if (j > K)
dp[i][j] = (dp[i][j] + (dp[i - 1][j] * (j - K)) % mod) % mod;
}
}
return (int) dp[L][N];
}
}