LeetCode 920. 播放列表的数量

2025-02-23 HGNULB 约 11 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 920. 播放列表的数量

题意分析

有 n 首互不相同的歌，要排出一个长度恰好为 goal 的播放列表，需要同时满足两条：每首歌至少播放一次；同一首歌两次播放之间，中间至少隔着 k 首其他的歌。问这样的播放列表有多少种，答案对 $10^9 + 7$ 取模。

「有多少种」加上「取模」，几乎锁死了这是计数题，不是构造题也不是搜索题——目标是数出方案数，不需要真的列举任何一个列表。

两条约束的性质完全不同。「每首歌至少一次」是全局约束，只有排完整个列表才能验证；「间隔至少 k 首」是局部约束，只跟最近 k 个位置有关。计数题里，把全局约束塞进状态维度、把局部约束塞进转移系数，是标准的拆解方式。

顺着这条思路看：列表是从左往右一个位置一个位置排的，排到某个位置时，真正影响后续的信息只有两件——已经排了多少个位置，以及已经用过多少首不同的歌。至于具体用了哪几首、它们怎么排列，由于所有歌是等价的（互不相同但地位对称），只需要知道个数，剩下的用乘法计数即可。

约束里 n、goal 最大 100，k < n <= goal。$O(n \cdot goal) = 10^4$ 的二维 DP 绰绰有余；同时 k < n 保证「隔 k 首」这个要求不至于自相矛盾。

边界：k = 0 时相当于没有间隔限制，答案是「用满 n 首歌的长度为 goal 的序列数」；goal = n 时每首歌恰好一次，答案是 n! 除去被间隔约束排除的部分（k = 0 时正好是 $n!$）。

解法：动态规划（滚动数组）

核心思路

先想暴力：枚举每个位置放哪首歌，用回溯保证间隔约束，最后检查是否每首都出现过。分支因子接近 n、深度 goal，是 $100^{100}$ 量级，完全不可能。

瓶颈在于回溯记住了「具体放了哪些歌、按什么顺序」，而这些细节里绝大部分对未来是无关的。真正影响后续选择的只有两个数：已排位置数、已用不同歌曲数。这就是把指数级压成多项式的关键——状态是对历史的有损压缩，只保留对未来有影响的部分。

状态定义：$dp[i][j]$ 表示「播放列表已排好前 i 个位置，其中恰好用到了 j 首互不相同的歌」的方案数。答案是 $dp[goal][n]$——长度排满 goal，且 n 首歌全部用上（这正是「每首至少一次」的全局约束落地成的那个维度值）。

初始条件：$dp[0][0] = 1$，空列表用了 0 首歌，算一种方案。其余 $dp[0][j] = 0$。

转移：看第 i 个位置放什么歌，只有两种互斥的来源。

第一种，放一首从未出现过的新歌。那么前 i-1 个位置用了 j-1 首不同的歌，方案数是 $dp[i-1][j-1]$；而这首新歌可以从剩下的 n - (j-1) 首里任选一首。所以贡献是 $dp[i-1][j-1] \times (n - j + 1)$。注意新歌一定合法——它此前从未播放，不受间隔约束。

第二种，重播一首已经出现过的旧歌。那么前 i-1 个位置已经用了 j 首不同的歌（这个位置不引入新歌），方案数是 $dp[i-1][j]$；可选的旧歌有多少首？已用过 j 首，但最近播放的 k 首歌不能再放（间隔不足），所以可选的是 $j - k$ 首。当 $j \le k$ 时没有任何旧歌可选，这一项为 0。所以贡献是 $dp[i-1][j] \times \max(j - k, 0)$。

「最近 k 首歌恰好是 k 首互不相同的歌」这一点需要确认：正因为间隔约束成立，最后 k 个位置上的歌必然两两不同，所以被禁用的恰好是 k 首，可选的恰好是 j - k 首。这是本题最巧妙的一步——局部约束被压缩成了一个只依赖 j 和 k 的系数，不需要在状态里记录「最近播了哪几首」。

合起来：
\[dp[i][j] = dp[i-1][j-1] \times (n - j + 1) + dp[i-1][j] \times \max(j - k,\, 0)\]
不变量：外层第 i 轮结束后，数组 dp 恰好等于「长度为 i 的合法前缀，按所用不同歌曲数分类的方案数」，且所有值都已对 $10^9+7$ 取模。

由于 $dp[i][\cdot]$ 只依赖 $dp[i-1][\cdot]$，可以用滚动数组把二维压成一维。这里采用「新建 newDp 再整体替换」的写法，而不是在原数组上倒序更新——转移同时用到了 dp[j-1] 和 dp[j] 两项，原地更新极易读到本轮已被改写的值，新建数组虽然多一次分配，但语义清晰、不会出错。

解题步骤

初始化 dp[0] = 1，其余为 0：对应 $dp[0][0] = 1$。这个 1 是所有计数的种子，漏掉它整张表全是 0。

外层 i 从 1 到 goal：一个位置一个位置地排，每轮把长度推进 1。

每轮新建 newDp（全 0）：$dp[i][0]$ 恒为 0（i >= 1 时至少用了一首歌），全 0 初始化正好覆盖这一点，不必单独写。

内层 j 从 1 到 min(i, n)：上界取 min(i, n) 是两个显然事实的合取——排了 i 个位置最多用 i 首不同的歌，同时总共也只有 n 首歌。超出这个范围的状态恒为 0，跳过它们能省掉大约一半的无效计算。

新歌转移 newDp[j] += dp[j-1] * (n - (j-1))：dp[j-1] 是上一轮的值（长度 i-1、用了 j-1 首），n - (j-1) 是可选新歌的首数。

旧歌转移，仅当 j > k：newDp[j] += dp[j] * (j - k)。用 if (j > k) 而不是写 max(j-k, 0)，是因为 j <= k 时整项为 0，直接跳过既省一次乘法又避免负数参与运算。

每步取模：两次累加后都 % mod。dp 用 long 存储，dp[j-1] 最大不超过 $10^9$，乘以最多 100 是 $10^{11}$，在 long 范围内安全；若用 int 则第一次乘法就溢出。

轮末 dp = newDp：滚动到下一层。

返回 (int) dp[n]：取 n 这个下标，正是「n 首歌全部用上」的那一列。返回 dp[goal] 或 dp[min(goal,n)] 都是审题错误。

以 n = 3、goal = 3、k = 1 走一遍，正确答案是 6。

初始：dp = [1, 0, 0, 0]（下标 0 到 3）。

i = 1（排第 1 个位置），upper = min(1,3) = 1。j = 1：新歌转移 newDp[1] = dp[0] * (3 - 0) = 1 * 3 = 3；j = 1 不大于 k = 1，旧歌项跳过。滚动后 dp = [0, 3, 0, 0]。含义：长度 1 的列表必然用了 1 首歌，3 种选法。

i = 2，upper = 2。j = 1：newDp[1] = dp[0] * 3 = 0 * 3 = 0（上一轮 dp[0] 已变成 0，因为长度 1 不可能用 0 首歌）；旧歌项因 j = 1 <= k 跳过。j = 2：新歌转移 newDp[2] = dp[1] * (3 - 1) = 3 * 2 = 6；j = 2 > k = 1，旧歌转移 += dp[2] * (2 - 1) = 0 * 1 = 0。滚动后 dp = [0, 0, 6, 0]。含义：长度 2 必须用两首不同的歌（因为 k = 1 禁止相邻重复），$3 \times 2 = 6$ 种。

i = 3，upper = 3。j = 1：dp[0] * 3 = 0。j = 2：新歌 dp[1] * 2 = 0，旧歌 dp[2] * (2-1) = 6 * 1 = 6，得 newDp[2] = 6——这 6 种是「用两首歌排三个位置」，第三个位置重播了一首非最近的旧歌。j = 3：新歌 dp[2] * (3 - 2) = 6 * 1 = 6；旧歌 dp[3] * (3-1) = 0。得 newDp[3] = 6。滚动后 dp = [0, 0, 6, 6]。

返回 dp[3] = 6。手工验证：三首歌各播一次，就是 3 的全排列共 6 种，且 k = 1 只禁止相邻相同，全排列里不存在相同元素相邻，所以 6 种全部合法，与结果一致。注意 dp[2] = 6 那一列被正确地排除在答案之外——它们只用了 2 首歌，违反「每首至少一次」。

再看旧歌系数为什么是 j - k 而不是 j - 1：把 k 改成 2 重算 i = 3, j = 3 那一步，新歌项仍是 6，而 j = 3 > k = 2，旧歌项是 dp[3] * (3-2)，此时 dp[3] 为 0；若误写成 j - 1，在更长的列表上会把「距离不足 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++) {
                newDp[j] = (newDp[j] + dp[j - 1] * (n - (j - 1))) % mod;
                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++ {
            newDp[j] = (newDp[j] + dp[j-1]*int64(n-(j-1))) % mod
            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)$。外层 goal 轮、内层最多 n 个状态，每个状态只做两次乘加与取模。代入上界是 $100 \times 100 = 10^4$，几乎瞬时。

空间复杂度：$O(n)$。滚动数组只保留相邻两层，各占 n + 1 个 long；不做滚动则是 $O(n \cdot goal)$，本题规模下也能接受，但滚动写法更能体现对依赖关系的把握。

关键点总结

计数题的第一步是设计状态：把「对未来有影响的信息」全部留下、其余全部丢掉。本题丢掉了「具体用了哪几首歌、怎么排」，只留下「长度」和「不同歌曲数」两个维度。

全局约束（每首至少一次）适合做成状态维度并在最终答案处取特定值；局部约束（间隔至少 k）适合做成转移系数。这个分工是组合计数 DP 的通用套路。

「最近 k 首必然互不相同」是本题最关键的一步推理——正因为约束成立，被禁用的恰好是 k 首，可选旧歌恰好 j - k 首，局部信息才不必进状态。

新歌系数 n - (j-1) 来自「从未用过的歌还剩几首」，旧歌系数 j - k 来自「用过的歌里有几首解禁」，两个系数的语义必须能一句话说清，否则一定会写错某一个。

全程用 64 位整数并每步取模：$10^9 \times 100$ 已超 int，先乘后模的中间值必须放得下。

面试视角：这题的得分点不在代码而在推导。能主动说出「歌曲之间是对称的，所以只需记个数」和「最近 k 首必然互不相同」两句话，基本就通过了；写不出闭式组合公式没关系，DP 是面试官期待的答案。

易错点总结

返回 dp[goal] 而不是 dp[n]：n = 3, goal = 3, k = 1 时两者恰好相同看不出问题，但 n = 2, goal = 3, k = 0 中 dp 数组长度只有 3，访问 dp[3] 直接越界。

漏掉 dp[0] = 1 的初始化：整张表全是 0，任何输入都返回 0。

新歌系数写成 n - j：n = 3, goal = 3, k = 1 的 i=1, j=1 一步会算成 1 * 2 = 2 而不是 3，最终答案变成 2 而正确答案是 6。

旧歌系数写成 j - 1 或 j：等于把间隔约束当成「只禁止相邻重复」或「完全不禁止」，n = 2, goal = 3, k = 1 会算出大于正确值的方案数。

旧歌转移不判 j > k：j = k 时系数为 0 尚且无害，j < k 时系数为负，会把方案数越减越小甚至出现负值。

内层上界只写 n 不取 min(i, n)：虽然多出的状态本身是 0 不影响正确性，但 i < j 的位置若被误当作有效状态参与后续转移（例如原地更新时），会引入根本不存在的方案。

在原数组上正序原地更新：dp[j] += dp[j-1] * ... 中的 dp[j-1] 已是本轮新值，等于允许「同一轮里连续加入两首新歌」，方案数严重偏大。必须新建数组或倒序更新。

用 int 存 dp 或不取模：dp[j-1] 接近 $10^9$ 时乘以 n 直接溢出成负数，n = 100, goal = 100, k = 0 会返回负数。

只在最后取一次模：中间值早已远超 long 上限，取模必须逐步进行。

把「间隔 k 首」理解成「间隔 k 个位置」：题目说的是中间必须夹着 k 首其他的歌，也就是两次播放的下标差至少是 k + 1；理解偏差会让 k 的所有系数整体错位一格。

忘记「每首歌至少播放一次」而对所有 j 求和：n = 3, goal = 3, k = 1 会把 dp[2] = 6 也加进去返回 12，正确答案是 6。

相似题目

题目	难度	考察点
629. K 个逆序对数组	困难	同为「按位置逐个放入 + 计数」的排列 DP，转移需前缀和优化
96. 不同的二叉搜索树	中等	计数 DP 的入门形态，按根节点划分左右规模，答案是卡塔兰数
377. 组合总和 Ⅳ	中等	求排列数而非组合数，循环顺序决定「顺序是否算不同方案」
518. 零钱兑换 II	中等	与 377 对照：外层枚举物品才是组合计数，是理解循环顺序语义的最佳例子
62. 不同路径	中等	最基础的方案数 DP，转移只有两项且无系数，适合作为状态设计的起点