https://leetcode.com/problems/number-of-music-playlists/
https://zhanghuimeng.github.io/post/leetcode-920-number-of-music-playlists/
https://blog.csdn.net/zjucor/article/details/82956847
Approach 1: Dynamic Programming
https://leetcode.com/problems/number-of-music-playlists/discuss/180338/DP-solution-that-is-Easy-to-understand
https://buptwc.github.io/2018/10/08/Leetcode-920-Number-of-Music-Playlists/
TODO
https://leetcode.com/articles/number-of-music-playlists/
Approach 2: Partitions + Dynamic Programming
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].
如果用DP来做,第一个问题是状态方程应该包含哪些变量。不妨先把状态方程设置成
dp[n][l][k]
。然后显然需要思考从哪些状态进行递推这个问题。我觉得之前我总会知道递归的状态的,但现在这好像是一个值得思考的问题。dp[n-1][l][k]
:比现在少一首歌,但播放列表长度仍然是l
。如何把多出来的歌塞进播放列表中是一个问题。dp[n][l-1][k]
:和现在歌的数量相同,但播放列表长度是l-1
。任何在[l-1-k, l-1]
位置没有被播放过的歌都可以被再播一遍;而且这一区间内的歌必然是没有重复的。这大概是此题的一个重要性质:合法的播放列表中,任何长度为k
的区间内的歌都是互不重复的。很好。所以答案+= dp[n][l-1][k] * (n - k)
。dp[n][l][k-1]
:因为破坏了之前的性质,所以感到很难用这个方法来递推。dp[n-1][l-1][k]
:比现在少一首歌,播放列表长度也少一首。把新歌插入到播放列表的任何位置都可以(不会缩小任何两首相同的歌之间的间隔),因此答案只需把新歌插入到播放列表的最后位置。这首歌可以是任意一首,因此答案+= dp[n-1][l-1][k] * (l + 1)
。+= dp[n-1][l-1][k] * n
。[1]
结论是,我们需要考虑的子状态只包括
dp[n][l-1][k]
和dp[n-1][l-1][k]
。由于题目中有N <= L
的要求,这一设置是合理的。同时,由于发现根本没有用到k
,不妨把k
去掉,得到dp[n][l-1]
和dp[n-1][l-1]
。
以及上面被划掉的部分说明我没有理解清楚此处DP到底意味着什么。DP的状态本身表示什么是很容易说明的:
dp[n][l]
表示长度为l
且有n
首不同的歌的播放列表的总数;而dp[n][l] += dp[n-1][l-1][k] * n
表示的是,从当前的n
首歌里任选一首删除,用n-1
首歌组成长度为l-1
的播放列表;最后再把选出来的这首歌放在播放列表最后。之所以不是把这首歌插入到播放列表的各个位置,是因为那样就会得到与其他歌重复的状态,因此需要加以限制。
显然上述代码还有很多可以优化的地方,包括但不限于[1]:
- 显然只有
j >= i
时f[i][j]
才有意义。 - 当
i == K + 1
时,意味着我们只能先播放K + 1
首歌曲,然后按相同顺序继续播放同样的歌曲,因此总的可能性数量为i!
。 - 当
i == j
时,歌曲数量和播放列表长度相同,不需要考虑K
的问题,因此总的可能性数量也为i!
。
思路: 如果先去掉 每首歌必须放一次 这个限制,用DP,dp[i]=dp[i-1]*(n-K)
如果加上这个限制,dp[n][l]表示已经听过了n首歌,一共放了l首歌的总数,dp[n][l]=dp[n-1][l-1]*n+dp[n][l-1]*(n-K)
https://leetcode.com/articles/number-of-music-playlists/Approach 1: Dynamic Programming
Let
dp[i][j]
be the number of playlists of length i
that have exactly j
unique songs. We want dp[L][N]
, and it seems likely we can develop a recurrence for dp
.
Algorithm
Consider
dp[i][j]
. Last song, we either played a song for the first time or we didn't. If we did, then we had dp[i-1][j-1] * (N-j)
ways to choose it. If we didn't, then we repeated a previous song in dp[i-1][j] * max(j-K, 0)
ways (j
of them, except the last K
ones played are banned.)- Time Complexity: .
- Space Complexity: . (However, we can adapt this algorithm to only store the last row of
dp
to easily get space complexity.)
public int numMusicPlaylists(int N, int L, int K) {
int MOD = 1_000_000_007;
long[][] dp = new long[L + 1][N + 1];
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);
dp[i][j] += dp[i - 1][j] * Math.max(j - K, 0);
dp[i][j] %= MOD;
}
return (int) dp[L][N];
}
https://leetcode.com/problems/number-of-music-playlists/discuss/180338/DP-solution-that-is-Easy-to-understand
dp[i][j] denotes the solution of i songs with j different songs. So the final answer should be dp[L][N]
Think one step before the last one, there are only cases for the answer of dp[i][j]
case 1 (the last added one is new song): listen i - 1 songs with j - 1 different songs, then the last one is definitely new song with the choices of N - (j - 1).
Case 2 (the last added one is old song): listen i - 1 songs with j different songs, then the last one is definitely old song with the choices of j
if without the constraint of K, the status equation will be
dp[i][j] = dp[i-1][j-1] * (N - (j-1)) + dp[i-1][j] * j
case 1 (the last added one is new song): listen i - 1 songs with j - 1 different songs, then the last one is definitely new song with the choices of N - (j - 1).
Case 2 (the last added one is old song): listen i - 1 songs with j different songs, then the last one is definitely old song with the choices of j
if without the constraint of K, the status equation will be
dp[i][j] = dp[i-1][j-1] * (N - (j-1)) + dp[i-1][j] * j
If with the constaint of K, there are also two cases
Case 1: no changes since the last added one is new song. Hence, there is no conflict
Case 2: now we don't have choices of j for the last added old song. It should be updated j - k because k songs can't be chosed from j - 1 to j - k. However, if j <= K, this case will be 0 because only after choosing K different other songs, old song can be chosen.
Case 1: no changes since the last added one is new song. Hence, there is no conflict
Case 2: now we don't have choices of j for the last added old song. It should be updated j - k because k songs can't be chosed from j - 1 to j - k. However, if j <= K, this case will be 0 because only after choosing K different other songs, old song can be chosen.
if (j > k)
dp[i][j] = dp[i-1][j-1] * (N- (j-1)) + dp[i-1][j] * (j-k)
else
dp[i][j] = dp[i-1][j-1] * (N- (j-1))
dp[i][j] = dp[i-1][j-1] * (N- (j-1)) + dp[i-1][j] * (j-k)
else
dp[i][j] = dp[i-1][j-1] * (N- (j-1))
public int numMusicPlaylists(int N, int L, int K) {
int mod = (int)Math.pow(10, 9) + 7;
long[][] dp = new long[L+1][N+1];
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;
if (j > K){
dp[i][j] = (dp[i][j] + (dp[i-1][j] * (j-K))%mod)%mod;
}
}
}
return (int)dp[L][N];
}
这道题一看像一个排列组合问题,熟悉排列组合的人对下面这个式子肯定不陌生
这个式子可以这样描述,在n个人里面挑选m个人,我们从挑不挑得到某个特定人X来考虑。
若挑得到,那么我们从剩下的n-1个人中再挑m-1个人。
若挑不到,那么我们从剩下的n-1个人中挑m个人。
这个式子可以这样描述,在n个人里面挑选m个人,我们从挑不挑得到某个特定人X来考虑。
若挑得到,那么我们从剩下的n-1个人中再挑m-1个人。
若挑不到,那么我们从剩下的n-1个人中挑m个人。
这道题也是用类似的思路,我们定义f(n,l,k)为题目所求,则有:
其中
f(n,l,k) = f(n-1,l-1,k) \* n + f(n,l-1,k) \* (n-k)
其中
f(n-1,l-1,k)
代表某个特定的歌只最后出现一次,其余n-1首歌填充了前面l-1个位置,因为有n首不同的歌所以乘n。f(n,l-1,k)
代表最后出现的某个特定的歌前面已经出现过了,这个最后出现的歌和当前最后k个位置的歌应当不相同,故乘(n-k)。
递推式已经找到,那么初始状态是什么呢?
显然当
当
显然当
n==l
时,则就是一个全排列,即为n!当
n > l or k > n
时,都不存在解,故为0
注意到在递推式中k其实始终无变化,所以实际定义dp时k可以省去
c(m,n)=c(m-1,n-1)+c(m-1,n)
等式左边表示从m个元素中选取n个元素,而等式右边表示这一个过程的另一种实现方法:任意选择m中的某个备选元素为特殊元素,从m中选n个元素可以由此特殊元素的被包含与否分成两类情况,即n个被选择元素包含了特殊元素和n个被选择元素不包含该特殊元素。前者相当于从m-1个元素中选出n-1个元素的组合,即c(m-1,n-1);后者相当于从m-1个元素中选出n个元素的组合,即c(m-1,n)。
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-920-number-of-music-playlists/
dp[i][j] := # of playlists of length i using j different songs.
dp[i][j] = dp[i – 1][j – 1] * (N – (j – 1)) + // Adding a new song. j – 1 used, choose any one from (N – (j – 1)) unused.
dp[i -1][j] * max(j – K, 0) // Reuse an existing song.
dp[i -1][j] * max(j – K, 0) // Reuse an existing song.
Time complexity: O(LN)
Space complexity: O(LN) -> O(N)
TODO
https://leetcode.com/articles/number-of-music-playlists/
Approach 2: Partitions + Dynamic Programming
Approach 3: Generating Functions