LeetCode 920. 播放列表的数量
题目描述
题意分析
用
n首不同歌曲组成长度为goal的播放列表，每首至少出现一次。重复播放某首歌前，必须先播放至少k首其他歌曲。统计满足这些条件的列表数量，并对1_000_000_007取模。要同时控制列表长度和是否用满全部歌曲，可以按“已排位置数”和“已经出现的不同歌曲数”计数；每个位置只需区分放入新歌还是旧歌。
解法：动态规划（滚动数组）
核心思路
[!blue]
定义
dp[i][j]为长度恰好为i、已经使用j首不同歌曲的合法列表数。若最后一个位置加入新歌，前面必然只用过j-1首，还能从未出现的n-(j-1)首中选择，因此贡献为dp[i-1][j-1]*(n-j+1)。若最后一个位置重播旧歌，前面就已经用过
j首。合法前缀最近的k首必然互不相同，否则其中某首歌的两次播放间隔不足要求；这k首暂时不能重播，其他旧歌都可以，因此可选数是j-k。当j<=k时没有可重播的旧歌，贡献为零。由此得到转移：
dp[i][j] = dp[i-1][j-1]*(n-j+1) + dp[i-1][j]*max(j-k,0)。不同前缀中受限制的具体歌曲可能不同，但可选数量相同，所以不必把最近歌曲的身份放进状态。新歌与旧歌两类互不重叠，删除最后一首又能唯一还原前缀，因此转移既不漏数也不重复计数。初值
dp[0][0]=1表示空列表这一种起点，其余状态为零。每层只依赖前一层，代码用dp保存旧长度的计数、newDp保存新长度的计数；每次取模后再进入下一轮。最终返回dp[n]，确保全部n首都至少出现一次，而不是把未用满歌曲的状态也加进答案。
解题步骤
- 初始化空列表的一种方案。
- 逐个增加播放位置，创建全零的新数组，只枚举
1到min(i,n)首已用歌曲。- 分别累加选新歌与重播合法旧歌的贡献并取模。
- 滚动到下一轮，最终返回 dp[n]。
k=0时所有已出现歌曲都可以重播，旧歌系数就是j；goal=n时为了用满歌曲，每个位置都必须加入新歌。前缀还不足k首时不能发生重复，对应的旧歌转移自然为零。
代码实现
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
long mod = 1_000_000_007L;
long[] dp = new long[n + 1];
// 空播放列表是一种方案，作为所有转移的起点。
dp[0] = 1;
for (int i = 1; i <= goal; i++) {
long[] newDp = new long[n + 1];
int upper = Math.min(i, n);
for (int j = 1; j <= upper; j++) {
// 加入新歌前已有 j-1 首，还能从其余 n-j+1 首中选择。
newDp[j] = (newDp[j] + dp[j - 1] * (n - (j - 1))) % mod;
// 最近 k 首不能重复，已用歌曲中只有 j-k 首可重新播放。
if (j > k) {
newDp[j] = (newDp[j] + dp[j] * (j - k)) % mod;
}
}
dp = newDp;
}
return (int) dp[n];
}
}
func numMusicPlaylists(n int, goal int, k int) int {
const mod int64 = 1_000_000_007
dp := make([]int64, n+1)
// 空播放列表是一种方案，作为所有转移的起点。
dp[0] = 1
for i := 1; i <= goal; i++ {
newDp := make([]int64, n+1)
upper := min920(i, n)
for j := 1; j <= upper; j++ {
// 加入新歌前已有 j-1 首，还能从其余 n-j+1 首中选择。
newDp[j] = (newDp[j] + dp[j-1]*int64(n-(j-1))) % mod
// 最近 k 首不能重复，已用歌曲中只有 j-k 首可重新播放。
if j > k {
newDp[j] = (newDp[j] + dp[j]*int64(j-k)) % mod
}
}
dp = newDp
}
return int(dp[n])
}
func min920(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n\cdot goal)$，包括每轮数组初始化和状态转移。
- 空间复杂度：$O(n)$，保存相邻两层。
关键点总结
[!green]
- 新歌增加不同歌曲数，旧歌保持该数量。
- 旧歌必须排除最近 k 首，不能简单乘 j。
- 最终只取全部歌曲都出现的状态，不对各 j 求和。
易错点总结
[!yellow]
- 空状态没有初始化为一：所有计数都无法启动。
- 新歌系数写成 n-j：少算尚未出现的歌曲。
- 正序原地更新状态：本轮可能反复读取刚更新的值。
- 乘法仍在窄整数中完成：取模前的乘积可能溢出。