class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
}
};
920. 播放列表的数量
你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复）。请你为她按如下规则创建一个播放列表：
K 首歌播放完之后才能再次播放。返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回它模 10^9 + 7 的结果。
示例 1：
输入：N = 3, L = 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, L = 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, L = 3, K = 1 输出：2 解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2]
提示：
0 <= K < N <= L <= 100原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 38 MB, 提交时间: 2023-08-16 17:13:27
class Solution {
public int numMusicPlaylists(int N, int L, int K) {
int MOD = 1_000_000_007;
// dp[S] at time P = <S, P> as discussed in article
long[] dp = new long[L-N+1];
Arrays.fill(dp, 1);
for (int p = 2; p <= N-K; ++p)
for (int i = 1; i <= L-N; ++i) {
dp[i] += dp[i-1] * p;
dp[i] %= MOD;
}
// Multiply by N!
long ans = dp[L-N];
for (int k = 2; k <= N; ++k)
ans = ans * k % MOD;
return (int) ans;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-08-16 17:12:25
'''
分类dp
记录每首歌首次播放时间
'''
class Solution:
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
# dp[S] at time P = <S, P> as discussed in article
dp = [1] * (goal-n+1)
for p in range(2, n-k+1):
for i in range(1, goal-n+1):
dp[i] += dp[i-1] * p
# Multiply by N!
ans = dp[-1]
for k in range(2, n+1):
ans *= k
return ans % (10**9 + 7)
golang 解法, 执行用时: 0 ms, 内存消耗: 4.1 MB, 提交时间: 2023-08-16 17:08:33
func numMusicPlaylists(n int, goal int, k int) int {
MOD := 1000000007
// dp[i][j] 播放列表长度为 i 包含恰好 j 首不同歌曲的数量
dp := make([][]int, goal+1)
for i, _ := range dp {
dp[i] = make([]int, n+1)
}
dp[0][0] = 1
for i := 1; i <= goal; i++ {
for j := 1; j <= n; j++ {
dp[i][j] += dp[i-1][j-1] * (n-j+1) // 最后一首歌未播放过, 从其他未播放里选
dp[i][j] += dp[i-1][j] * max(j-k, 0) // 最后一首歌播放过，从之前的里面选
dp[i][j] %= MOD
}
}
return dp[goal][n]
}
func max(x, y int) int { if x > y { return x }; return y }
java 解法, 执行用时: 6 ms, 内存消耗: 39.9 MB, 提交时间: 2023-08-16 17:03:10
class Solution {
public int numMusicPlaylists(int N, int L, int K) {
int MOD = 1_000_000_007;
// dp[i][j] 播放列表长度为 i 包含恰好 j 首不同歌曲的数量
long[][] dp = new long[L+1][N+1];
dp[0][0] = 1;
for (int i = 1; i <= L; ++i)
for (int j = 1; j <= N; ++j) {
dp[i][j] += dp[i-1][j-1] * (N-j+1); // 最后一首歌未播放过, 从其他未播放里选
dp[i][j] += dp[i-1][j] * Math.max(j-K, 0); // 最后一首歌播放过，从之前的里面选
dp[i][j] %= MOD;
}
return (int) dp[L][N];
}
}
python3 解法, 执行用时: 136 ms, 内存消耗: 19.2 MB, 提交时间: 2023-08-16 17:01:13
'''
N = 总数
L = 队列长度
K = 延后次数
令 dp[i][j] 为播放列表长度为 i 包含恰好 j 首不同歌曲的数量, 要计算 dp[L][N].
'''
from functools import lru_cache
class Solution:
def numMusicPlaylists(self, N, L, K):
@lru_cache(None)
def dp(i, j):
if i == 0:
return +(j == 0)
ans = dp(i-1, j-1) * (N-j+1) # 最后一首歌未播放过
ans += dp(i-1, j) * max(j-K, 0) # 最后一首歌播放过
return ans % (10**9+7)
return dp(L, N)