Hard

题目描述

你的音乐播放器里有 n 首不同的歌曲。你想在旅途中听 goal 首歌（不一定不同）。为了避免无聊，你需要创建一个播放列表，满足以下条件：

  • 每首歌至少播放一次
  • 一首歌只有在播放了 k 首其他歌曲后才能再次播放

给定 n、goal 和 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 = 0
输出：6
解释：有 6 种可能的播放列表：[1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], 和 [1, 2, 2]。

示例 3：

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

约束条件：

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

解题思路

这是一个经典的动态规划问题，需要仔细分析状态转移。

核心思路： 定义 dp[i][j] 表示播放了 i 首歌，其中有 j 首不同歌曲的方案数。

状态转移分析： 对于当前位置，我们有两种选择：

  1. 播放新歌：如果当前已有 j-1 首不同歌曲，那么可以选择剩余的 n-(j-1) 首新歌中的任意一首
  2. 重复播放旧歌：如果当前已有 j 首不同歌曲，且满足间隔要求（即 j > k），那么可以选择之前播放过的 j-k 首歌

状态转移方程：

dp[i][j] = dp[i-1][j-1] * (n - (j-1)) + dp[i-1][j] * max(0, j-k)

边界条件：

  • dp[0][0] = 1（基础情况）
  • 其他 dp[0][j] = 0

优化思路： 由于每次状态转移只依赖前一行，可以使用滚动数组优化空间复杂度。但考虑到约束条件较小（goal ≤ 100），直接使用二维数组即可。

代码实现

class Solution {
public:
    int numMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1e9 + 7;
        vector<vector<long long>> dp(goal + 1, vector<long long>(n + 1, 0));
        
        dp[0][0] = 1;
        
        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= min(i, 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;
                }
            }
        }
        
        return dp[goal][n];
    }
};

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        MOD = 10**9 + 7
        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):
                # 播放新歌
                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
        
        return dp[goal][n]

public class Solution {
    public int NumMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1000000007;
        long[,] dp = new long[goal + 1, n + 1];
        
        dp[0, 0] = 1;
        
        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= Math.Min(i, 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;
                }
            }
        }
        
        return (int)dp[goal, n];
    }
}

var numMusicPlaylists = function(n, goal, k) {
    const MOD = 1e9 + 7;
    const dp = Array(goal + 1).fill(null).map(() => Array(n + 1).fill(0));
    
    dp[0][0] = 1;
    
    for (let i = 1; i <= goal; i++) {
        for (let j = 1; j <= Math.min(i, 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;
            }
        }
    }
    
    return dp[goal][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(goal × n)需要填充 goal × n 的二维数组
空间复杂度O(goal × n)存储动态规划状态的二维数组

相关题目