播放列表的数量Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

每首歌至少播放一次。
一首歌只有在其他 k 首歌播放完之后才能再次播放。给你 n、goal 和 k ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 109 + 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

# 思路

long[][] dp = new long[g + 1][n + 1];

# 解法

class Solution {
    public int numMusicPlaylists(int n, int g, int k) {
        int MOD = (int) (1e9 + 7);
        // 播放了i首歌，一共播放了j种不同的歌,
        long[][] dp = new long[g + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= g; i++) {
            for (int j = 1; j <= n; j++) {
                // 第i首歌是新歌, 听过的歌种类要加1 , 所以 j 需要从 j - 1 转移过来
                long sit1 = ((dp[i - 1][j - 1] * (n - (j - 1)))) % MOD;
                // 第i首是重复的歌，听过的歌种类不变，所以 j 不变
                long sit2 = dp[i - 1][j] * Math.max(0, (j - k)) % MOD;
                dp[i][j] = (sit1 + sit2) % MOD;
            }
        }
        return (int) dp[g][n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 总结

分析出几种情况，然后分别对各个情况实现