播放列表的数量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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 总结
- 分析出几种情况，然后分别对各个情况实现
