---

0920. 播放列表的数量

• 标签：数学、动态规划、组合数学
• 难度：困难

题目链接

• 0920. 播放列表的数量 - 力扣

题目大意

描述：

你的音乐播放器里有 $n$ 首不同的歌，在旅途中，你计划听 $goal$ 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：

• 每首歌「至少播放一次」。
• 一首歌只有在其他 $k$ 首歌播放完之后才能再次播放。

给定 $n$、$goal$ 和 $k$。

要求：

返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 $10^9 + 7$ 取余 的结果。

说明：

• $0 \le k \lt n \le goal \le 10^{3}$。

示例：

• 示例 1：

输入：n = 3, goal = 3, k = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] 。

• 示例 2：

输入：n = 2, goal = 3, k = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2] 。

解题思路

思路 1：动态规划

这是一个经典的组合计数问题，需要使用动态规划来解决。

1. 状态定义：$dp[i][j]$ 表示长度为 $i$、包含 $j$ 首不同歌曲的播放列表数量。
2. 状态转移：对于 $dp[i][j]$，考虑第 $i$ 首歌的选择：
   • 选择新歌：从剩余的 $n - j + 1$ 首歌中选择，转移方程：$dp[i][j] = dp[i-1][j-1] \times (n - j + 1)$
   • 选择旧歌：必须是 $k$ 首歌之前播放过的，即至少有 $j - k$ 首歌可选，转移方程：$dp[i][j] = dp[i-1][j] \times \max(j - k, 0)$
3. 初始化：$dp[0][0] = 1$（空播放列表）。
4. 返回结果：$dp[goal][n]$。

思路 1：代码

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        MOD = 10**9 + 7
        
        # dp[i][j] 表示长度为 i、包含 j 首不同歌曲的播放列表数量
        dp = [[0] * (n + 1) for _ in range(goal + 1)]
        dp[0][0] = 1
        
        for i in range(1, goal + 1):
            for j in range(1, min(i, n) + 1):
                # 选择新歌：从 n - j + 1 首歌中选择
                dp[i][j] = dp[i - 1][j - 1] * (n - j + 1) % MOD
                
                # 选择旧歌：从已播放的 j 首歌中选择（需要满足 k 首歌的限制）
                if j > k:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD
        
        return dp[goal][n]

思路 1：复杂度分析

• 时间复杂度：$O(goal \times n)$，需要填充 $goal \times n$ 的 DP 表。
• 空间复杂度：$O(goal \times n)$，需要使用二维数组存储 DP 状态。可以优化为 $O(n)$（滚动数组）。