题目描述

你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即允许歌曲重复）。请你为她按如下规则创建一个播放列表：

• 每首歌至少播放一次。
• 一首歌只有在其他 K 首歌播放完之后才能再次播放。

返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回它模 10^9 + 7 的结果。

样例

输入：N = 3, L = 3, K = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1].

输入：N = 2, L = 3, K = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2]

输入：N = 2, L = 3, K = 1
输出：2
解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2]

算法

(动态规划) $O(NL)$

1. 状态 $f(i, j)$ 表示前 $i$ 次播放了 $j$ 首不同歌曲的方案数。
2. 对于 $f(i, j)$，当前有两种选择：(1) 播放一首新的歌曲。前 $i-1$ 次播放了 $j-1$ 首不同的歌曲之后，第 $i$ 次播放前还有 $N-j+1$ 首不同的歌曲没有播放，根据乘法原理 $f(i, j) = f(i, j) + f(i - 1, j - 1) * (N-j+1)$。(2) 播放一首重复的歌曲。考虑前 $i-1$ 次播放了 $j$ 首不同的歌曲，对于之前的每种播放列表，我们可以重复列表前 $j-K$ 歌曲中的某一首。如果 $j-K<0$ 则无法重复播放。根据乘法原理，$f(i, j) = f(i, j) + f(i - 1, j) * max(j - K, 0)$。
3. $i$ 和 $j$ 的下标都是从 1 开始；初始值 $f(0, 0) = 1$；最终答案为 $f(L, N)$。

时间复杂度

• 共有 $NL$ 个状态，每个状态有 2 种转移，故时间复杂度为 $O(NL)$。

C++ 代码

#define LL long long
class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        const int mod = 1000000007;
        vector<vector<int>> f(L + 1, vector<int>(N + 1, 0));

        f[0][0] = 1;

        for (int i = 1; i <= L; i++)
            for (int j = 1; j <= N; j++) {
                f[i][j] = (f[i][j] + (LL)(f[i - 1][j - 1]) * (N - j + 1)) % mod;
                f[i][j] = (f[i][j] + (LL)(f[i - 1][j]) * max(j - K, 0)) % mod;
            }

        return f[L][N];
    }
};