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
Accepted
13,936
Submissions
29,137
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { long M = 1000000000+7; public int numMusicPlaylists(int N, int L, int K) { long[][] dp = new long[L][N]; for(int j=0; j<N; ++j){ dp[0][j] = j==0?N:0; } for(int i=1; i<L; ++i){ dp[i][0] = K==0?N:0; } for(int i=1; i<L; ++i){ for(int j=1; j<N; ++j){ dp[i][j] = dp[i-1][j-1]*(N-j)%M; if(j+1-K>0) dp[i][j] = (dp[i][j] + dp[i-1][j]*(j+1-K)%M)%M; } } return (int)dp[L-1][N-1]; } } |
No comments:
Post a Comment