Leetcode 920 Number of Music Playlists

920.Number of Music Playlists

题目大意

N首歌曲,总共需要演奏L次歌曲,每首歌都要被演奏过,一首歌被演奏过后K次后才可以再次演奏,求最终的方案数(mod 1e9+7).

0 <= K < N <= L <= 100

样例

1
2
3
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].
1
2
3
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]
1
2
3
Input: N = 2, L = 3, K = 1
Output: 2
Explanation: There are 2 possible playlists. [1, 2, 1], [2, 1, 2]

分析

第一眼感觉是个DP…但是好久没写了感觉很自闭…

还好努力了一下云出了公式诶….

这类问题的递推,从第N-1首到第N首的情况下,状态的变化取决于第N首是否被选取(每首歌必须被选一次可以暂时忽略)

我们可以发现这个K实际上只常亮没啥区别 可以直接拿掉

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static const int MOD = 1000000007;
class Solution {
public:
int numMusicPlaylists(int N, int L, int K) {
long long int dp[N + 1][L + 1];
memset(dp,0,sizeof(dp));
dp[1][1] = 1;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= L; j++) {
dp[i][j] += dp[i][j-1] * max(i - K, 0) + dp[i-1][j-1] * i;
dp[i][j] %= MOD;
}
return dp[N][L];
}
};