Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/920.html
920. Number of Music Playlists (Hard)
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
Related Topics:
Dynamic Programming
Solution 1. DP
Let dp[i][j]
be the number of playlists of length i
that have exactly j
unique songs. The answer is dp[L][N]
.
To get dp[i][j]
, we consider the i-1
-th song:
- It has not been played before. This is the first time it’s played. The first
i - 1
songs must havej - 1
unique songs. We can choose fromN - (j - 1)
new songs. Sodp[i - 1][j - 1] * (N - j + 1)
cases. - It has been played before. The first
i - 1
songs must havej
unique songs. This song is one of thej
unique songs. The[i - K, i - 1]
songs must be unique and the last song can’t be of theseK
songs. So we can only choose from the remainingj - K
songs.dp[i - 1][j] * max(j - K, 0)
// OJ: https://leetcode.com/problems/number-of-music-playlists/
// Time: O(NL)
// Space: O(NL)
// Ref: https://leetcode.com/problems/number-of-music-playlists/solution/
class Solution {
public:
int numMusicPlaylists(int N, int L, int K) {
long dp[101][101] = {}, mod = 1e9+7;
dp[0][0] = 1;
for (int i = 1; i <= L; ++i) {
for (int j = 1; j <= N; ++j) {
dp[i][j] += dp[i - 1][j - 1] * (N - j + 1);
dp[i][j] += dp[i - 1][j] * max(j - K, 0);
dp[i][j] %= mod;
}
}
return dp[L][N];
}
};
-
class Solution { public int numMusicPlaylists(int N, int L, int K) { final int MODULO = 1000000007; long[][] dp = new long[L + 1][N + 1]; dp[0][0] = 1; for (int i = 1; i <= L; i++) { for (int j = 1; j <= N; j++) { dp[i][j] += dp[i - 1][j - 1] * (N - j + 1) + dp[i - 1][j] * Math.max(j - K, 0); dp[i][j] %= MODULO; } } return (int) dp[L][N]; } } ############ 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]; } }
-
// OJ: https://leetcode.com/problems/number-of-music-playlists/ // Time: O(NL) // Space: O(NL) // Ref: https://leetcode.com/problems/number-of-music-playlists/solution/ class Solution { public: int numMusicPlaylists(int N, int L, int K) { long dp[101][101] = {}, mod = 1e9+7; dp[0][0] = 1; for (int i = 1; i <= L; ++i) { for (int j = 1; j <= N; ++j) { dp[i][j] += dp[i - 1][j - 1] * (N - j + 1); dp[i][j] += dp[i - 1][j] * max(j - K, 0); dp[i][j] %= mod; } } return dp[L][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[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] }
-
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]; }