920.播放列表数量

播放列表数量

你的音乐播放器里有 n 首不同的歌，你在旅途中听歌。你希望旅途中听到的歌的数量尽可能多。

给你整数 n 、goal 和 k ，返回长度为 goal 的播放列表的数量：

• 播放列表中必须包含 n 首不同的歌。
• 播放列表中的歌不能重复，除非两首歌之间的间隔至少为 k 首其他歌。

由于答案可能很大，返回结果对 10^9 + 7 取余。

示例 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 = 1
输出：2
解释：有 2 种可能的播放列表：[1,2,1]，[2,1,2]

示例 3：

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

提示：

• 0 <= k < n <= goal <= 100

解析

使用动态规划，dp[i][j] 表示播放列表长度为 i，包含 j 首不同歌的方案数。

var numMusicPlaylists = function (n, goal, k) {
  const MOD = 1e9 + 7;
  const dp = Array.from({ length: goal + 1 }, () => new Array(n + 1).fill(0));
  dp[0][0] = 1;

  for (let i = 1; i <= goal; i++) {
    for (let j = 1; j <= n; j++) {
      // 播放一首新歌
      dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * (n - j + 1)) % MOD;
      // 播放一首旧歌（需要间隔 k 首）
      if (j > k) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD;
      }
    }
  }

  return dp[goal][n];
};

时间复杂度 O(goal × n)，空间复杂度 O(goal × n)。