Leetcode 920: Number of Music Playlists

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

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

Notes:

This question is not easy to find a solution, so usually it can be solved by dp.

The key is to find the logic. If we define

dp[i][j] represents the number of list with i songs using j different songs, then

dp[i][j] = dp[i-1][j-1] * (N - (j-1)) + dp[i-1][j] *(j - K).

The first term on the right side: if we choose a new song as the jth song, we have (N - (j-1)) choices;

The second term: if we choose an old song as the jth song, we have (j - K) choices.

See the code below:

class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        int mod = 1e9+7;
        vector<vector<long>> dp(L+1, vector<long>(N+1, 0));
        //dp[i][j]: the number of list of i songs with j different songs
        //dp[i][j] = dp[i-1][j-1] * (N - (j - 1)) + dp[i-1][j] * j;  when K == 0;
        //dp[i][j] = dp[i-1][j-1] * (N - (j - 1)) + dp[i-1][j] * (j - K);
        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) : 0) % mod ) % mod;
            }
        }
        return dp[L][N];
    }
};