920. Number of Music Playlists

dp O(NL) time O(NL) space
这道题的建模应该先从如何生成一个播放列表入手，因为有K首歌之内不能重复这个限制条件，所以我们一定是要一首歌一首歌往播放列表里添加并且每次都要检查是否跟前K首歌重复，如果重复则选择另外一首歌，所以我们只考虑不重复的合法情况：

1. 跟当前已生成的播放列表完全不重复，这样的歌就是所有还未选择过的歌
2. 跟前K首歌不重复但是跟K首歌之前的歌有重复，这样的歌就是已经被选择过的播放列表中的歌但是并不在最近的K首歌里

假设dp[l][n]表示对于播放表的前l首歌，去除重复的歌曲后还剩下n首歌的方案数。（即使用n首歌来生成播放表的前l首歌）

那么需要return的答案便为：dp[L][N] (因为每首歌必须至少出现一次，故这L首歌去除重复后一定有N首歌)

对于dp[l][n]的求解，需要分类讨论：

1. 播放表的第l首歌跟前面的(l - 1)首都不一样，则对于dp[l][n]，我们可以先使用(n - 1)首歌排好播放表的前(l - 1)首歌，然后从剩下的(N - (n - 1))首歌
   里面再任意取一首歌，放在第l个位置，即：
   dp[l][n] += dp[l - 1][n - 1] * (N - (n - 1))

2. 播放表的第l首歌跟前面的(l - 1)首存在重复的，则对于dp[l][n]，我们可以先使用n首歌排好前面的(l - 1)首歌，然后因为保证任意两首相同的歌之间至
   少有k首不同的歌，故对于dp[l - 1][n]里面的方案，最后的k首歌一定不一样，故我们只需要选一首跟最后面的k首歌不一样的歌，放在第l个位置即可，即：
   dp[l][n] += dp[l - 1][n] * (n - k)

此题得解，时间复杂度:O(NL)
注意一开始的初始化：dp[0][0] = 1

class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        int M = 1e9 + 7;
        vector<vector<long>> f(L + 1, vector<long>(N + 1));
        f[0][0] = 1;
        for (int l = 1; l <= L; ++l) {
            for (int n = 1; n <= N; ++n) {
                f[l][n] = (f[l][n] + f[l - 1][n - 1] * (N - (n - 1))) % M;
                f[l][n] = (f[l][n] + f[l - 1][n] * max(0, n - K)) % M;
            }
        }
        return f[L][N];
    }
};