920. Number of Music Playlists

Problem

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:

0 <= K < N <= L <= 100

Problem Restatement

Your music player has N different songs. During the trip, your companion wants to listen to L songs (not necessarily different; that is, songs may be repeated). Please create a playlist for her according to the following rules:

Every song is played at least once.
A song can only be played again after K other songs have been played.

Return the number of playlists that satisfy the requirements. Since the answer may be very large, return the result modulo 10^9 + 7.

Note:

0 <= K < N <= L <= 100

Solution Approach

To simplify and abstract the problem: given N numbers, form a sequence of length L from these N numbers, and the distance between identical elements cannot be less than K numbers. Ask how many ways there are in total.
At first glance, this problem may seem like a three-dimensional DP because there are 3 variables, but after thinking about it, one dimension can be reduced. First, ignore the constraint K and only consider N and L. Define dp[i][j] to represent that the playlist has i songs and contains j different songs, so the final answer required by the problem is in dp[L][N]. Consider the recurrence formula for dp[i][j]: the current playlist needs to consist of i songs, and there are 2 ways to obtain it: add a new song that does not exist in the playlist to a playlist of i - 1 songs, or add a song that already exists in the playlist to a playlist of i - 1 songs. That is, dp[i][j] can be obtained from dp[i - 1][j - 1], or from dp[i - 1][j]. In the first case, adding a new song, there are N - ( j - 1 ) choices for the new song; in the second case, adding an already existing song, there are j choices, so the state transition equation is dp[i][j] = dp[i - 1][j - 1] * ( N - ( j - 1 ) ) + dp[i - 1][j] * j. However, this equation is derived without considering the constraint K, so it is still one step away from satisfying the problem requirements. Next, we need to consider how to derive the state transition equation after adding the constraint K.
If adding a new song, it is not restricted by K, so dp[i - 1][j - 1] * ( N - ( j - 1 ) ) does not need to change. If adding an existing song, it will be restricted by K at this point. If the current playlist contains j songs and j > K, then the song can only be chosen from j - K songs, because the songs from j - 1 to j - k cannot be chosen; choosing them would violate the constraint that the interval between repeated songs cannot be less than K. What about j ≤ K? At this point, no song can be chosen, because the number of songs has not exceeded K, so of course a repeated song cannot be chosen. (Choosing one would again violate the constraint that the interval between repeated songs cannot be less than K.) Based on the above analysis, the final state transition equation can be obtained: {{< katex display >}} dp[i][j]= \begin{matrix} \left{ \begin{array}{lr} dp[i - 1][j - 1] * ( N - ( j - 1 ) ) + dp[i - 1][j] * ( j - k ) , & {j > k}\ dp[i - 1][j - 1] * ( N - ( j - 1 ) ), & {j \leq k} \end{array} \right. \end{matrix} {{< /katex >}}
The above formula can be merged and simplified into the following formula: dp[i][j] = dp[i - 1][j - 1]*(N - (j - 1)) + dp[i-1][j]*max(j-K, 0), with the initial recursive value dp[0][0] = 1.

Code


package leetcode

func numMusicPlaylists(N int, L int, K int) int {
	dp, mod := make([][]int, L+1), 1000000007
	for i := 0; i < L+1; i++ {
		dp[i] = make([]int, N+1)
	}
	dp[0][0] = 1
	for i := 1; i <= L; i++ {
		for j := 1; j <= N; j++ {
			dp[i][j] = (dp[i-1][j-1] * (N - (j - 1))) % mod
			if j > K {
				dp[i][j] = (dp[i][j] + (dp[i-1][j]*(j-K))%mod) % mod
			}
		}
	}
	return dp[L][N]
}