920. Number of Music Playlists

Your music player contains N different songs and she wants to listen to L (not necessarily different) songs during your trip. You create a playlist so that:

• Every song is played at least once

• A song can only be played again only if K other songs have been played

Return the number of possible playlists. As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

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].

Example 2:

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]

Example 3:

Input: N = 2, L = 3, K = 1
Output: 2
Explanation: There are 2 possible playlists. [1, 2, 1], [2, 1, 2]

Note:

1. 0 <= K < N <= L <= 100

需要一個2D DP table，dp[i][j]代表播的i首歌裡有j首不同的歌的總可能播放清單數量。分成兩種情況考慮，分別是最後一首加入清單的歌是否是第一次出現的歌。如果是新歌，那麼就有可能有dp[i - 1][j - 1]乘以剩下沒出現過的歌的數量(N - (j - 1))。如果是舊歌，那麼要考慮總共j首不同的歌是否大於每首歌可以重複被播放只要撥了其他K首歌。如果j <= K代表不可能有這種情形，所以是0。如果j > K，代表可以從播過的歌中選出j - K種情形，所以是dp[i - 1][j] * (j - K)。

// Dynamic Programming
int numMusicPlaylists(int N, int L, int K) { // time: O(L * N); space: O(L * N)
    int mod = 1e9 + 7;
    // dp[i][j]: total number of possible playlists from i songs with j different songs
    // Final answer is dp[L][N]
    // dp state transition:
    // 1. The last added song is new: dp[i - 1][j - 1] * (N - (j - 1))
    // 2. The last added song is old: dp[i - 1][j] * (j - K) if j > K, otherwise, 0
    // dp[i][j] = dp[i - 1][j - 1] * (N - (j - 1)) + dp[i - 1][j] * (j - K)
    vector<vector<long> > dp(L + 1, vector<long> (N + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= L; ++i) {
        for (int j = 1; j <= N; ++j) {
            dp[i][j] = (dp[i - 1][j - 1] * (N - (j - 1)) % mod + ((j > K) ? (dp[i - 1][j] * (j - K)) % mod : 0)) % mod;
        }
    }
    return (int)dp[L][N];
}