Problem
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
Solution: DP
dp[i][j] := # of playlists of length i using j different songs.
dp[i][j] = dp[i – 1][j – 1] * (N – (j – 1)) + // Adding a new song. j – 1 used, choose any one from (N – (j – 1)) unused.
dp[i -1][j] * max(j – K, 0) // Reuse an existing song.
Time complexity: O(LN)
Space complexity: O(LN) -> O(N)
C++/O(LN)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int numMusicPlaylists(int N, int L, int K) { constexpr long kMod = 1e9 + 7; vector<vector<long>> dp(L + 1, vector<long>(N + 1, 0)); dp[0][0] = 1; for (int i = 1; i <= L; ++i) for (int j = 1; j <= min(i, N); ++j) dp[i][j] = (dp[i - 1][j - 1] * (N - (j - 1)) + dp[i - 1][j] * max(j - K, 0)) % kMod; return dp[L][N]; } }; |
C++/O(N)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua, 0 ms class Solution { public: int numMusicPlaylists(int N, int L, int K) { constexpr long kMod = 1e9 + 7; vector<long> dp(N + 1, 0); for (int i = 1; i <= L; ++i) { dp[0] = i == 1; for (int j = min(i, N); j >= 1; --j) dp[j] = (dp[j - 1] * (N - (j - 1)) + dp[j] * max(j - K, 0)) % kMod; } return dp[N]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment