vegatable

0%

Leetcode 920 Number of Music Playlists

发表于 阅读次数： Valine：
本文字数： 921 阅读时长 ≈ 2 分钟

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首是否被选取（每首歌必须被选一次可以暂时忽略）
$$
f(n,l,k)=f(n-1,l-1,k)n+f(n,l-1,k)(n-k)
$$
我们可以发现这个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];
    }
};