920. Number of Music Playlists

https://leetcode.com/problems/number-of-music-playlists/

N首不同的歌选L个使得每首歌至少被选一次，且重复选歌时要求已经有选K首不同的歌，问最后有多少种选法。分成L步，每步action为选新歌还是旧歌，受限于已经有多少首不同的歌选过。因此dp[i][j]表示从j首歌中选出i个。选新歌时前面j - 1首选i-1首新歌有dp[i-1][j-1]种选法，不管前面具体用哪种，选定后i还有N-(j - 1)种选法，因此i选新歌时总共有dp[i -1][j -1]*(N -(j -1))选法；不选新歌时前面有dp[i-1][j]种选法，从比K多的j-K首中选有j-K种，依然用乘法法则相乘。

/*
 * @lc app=leetcode id=920 lang=cpp
 *
 * [920] Number of Music Playlists
 */

// @lc code=start
class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        const long M = 1e9 + 7;
        vector<vector<long>> dp(L + 1, vector<long>(N + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= L; ++i) {
            for (int j = 1; j <= min(i, N); ++j) {
                // Add new song or not.
                dp[i][j] = dp[i - 1][j - 1] * (N - (j - 1)) % M + dp[i - 1][j] * max(j - K, 0) % M;
                dp[i][j] %= M;
            }
        }
        return dp[L][N];
    }
};
// @lc code=end