920. 播放列表的数量
题目描述
你的音乐播放器里有 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
解法
方法一：动态规划
我们定义 $f[i][j]$ 表示听 $i$ 首歌，且这 $i$ 首歌中有 $j$ 首不同歌曲的播放列表的数量。初始时 $f[0][0]=1$。答案为 $f[goal][n]$。
对于 $f[i][j]$，我们可以选择没听过的歌，那么上一个状态为 $f[i - 1][j - 1]$，这样的选择有 $n - (j - 1) = n - j + 1$ 种，因此 $f[i][j] += f[i - 1][j - 1] \times (n - j + 1)$。我们也可以选择听过的歌，那么上一个状态为 $f[i - 1][j]$，这样的选择有 $j - k$ 种，因此 $f[i][j] += f[i - 1][j] \times (j - k)$，其中 $j \geq k$。
综上，我们可以得到状态转移方程：
$$ f[i][j] = \begin{cases} 1 & i = 0, j = 0 \ f[i - 1][j - 1] \times (n - j + 1) + f[i - 1][j] \times (j - k) & i \geq 1, j \geq 1 \end{cases} $$
最终的答案为 $f[goal][n]$。
时间复杂度 $O(goal \times n)$，空间复杂度 $O(goal \times n)$。其中 $goal$ 和 $n$ 为题目中给定的参数。
Python3
class Solution:
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
mod = 10**9 + 7
f = [[0] * (n + 1) for _ in range(goal + 1)]
f[0][0] = 1
for i in range(1, goal + 1):
for j in range(1, n + 1):
f[i][j] = f[i - 1][j - 1] * (n - j + 1)
if j > k:
f[i][j] += f[i - 1][j] * (j - k)
f[i][j] %= mod
return f[goal][n]
Java
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
final int mod = (int) 1e9 + 7;
long[][] f = new long[goal + 1][n + 1];
f[0][0] = 1;
for (int i = 1; i <= goal; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = f[i - 1][j - 1] * (n - j + 1);
if (j > k) {
f[i][j] += f[i - 1][j] * (j - k);
}
f[i][j] %= mod;
}
}
return (int) f[goal][n];
}
}
C++
class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
const int mod = 1e9 + 7;
long long f[goal + 1][n + 1];
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 1; i <= goal; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = f[i - 1][j - 1] * (n - j + 1);
if (j > k) {
f[i][j] += f[i - 1][j] * (j - k);
}
f[i][j] %= mod;
}
}
return f[goal][n];
}
};
Go
func numMusicPlaylists(n int, goal int, k int) int {
const mod = 1e9 + 7
f := make([][]int, goal+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i := 1; i <= goal; i++ {
for j := 1; j <= n; j++ {
f[i][j] = f[i-1][j-1] * (n - j + 1)
if j > k {
f[i][j] += f[i-1][j] * (j - k)
}
f[i][j] %= mod
}
}
return f[goal][n]
}
TypeScript
function numMusicPlaylists(n: number, goal: number, k: number): number {
const mod = 1e9 + 7;
const f = new Array(goal + 1).fill(0).map(() => new Array(n + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= goal; ++i) {
for (let j = 1; j <= n; ++j) {
f[i][j] = f[i - 1][j - 1] * (n - j + 1);
if (j > k) {
f[i][j] += f[i - 1][j] * (j - k);
}
f[i][j] %= mod;
}
}
return f[goal][n];
}
Rust
impl Solution {
#[allow(dead_code)]
pub fn num_music_playlists(n: i32, goal: i32, k: i32) -> i32 {
let mut dp: Vec<Vec<i64>> = vec![vec![0; n as usize + 1]; goal as usize + 1];
// Initialize the dp vector
dp[0][0] = 1;
// Begin the dp process
for i in 1..=goal as usize {
for j in 1..=n as usize {
// Choose the song that has not been chosen before
// We have n - (j - 1) songs to choose
dp[i][j] += dp[i - 1][j - 1] * ((n - ((j as i32) - 1)) as i64);
// Choose the song that has been chosen before
// We have j - k songs to choose if j > k
if (j as i32) > k {
dp[i][j] += dp[i - 1][j] * (((j as i32) - k) as i64);
}
// Update dp[i][j]
dp[i][j] %= ((1e9 as i32) + 7) as i64;
}
}
dp[goal as usize][n as usize] as i32
}
}
方法二：动态规划（空间优化）
我们注意到 $f[i][j]$ 只与 $f[i - 1][j - 1]$ 和 $f[i - 1][j]$ 有关，因此我们可以使用滚动数组优化空间复杂度，将空间复杂度优化至 $O(n)$。
Python3
class Solution:
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
mod = 10**9 + 7
f = [0] * (goal + 1)
f[0] = 1
for i in range(1, goal + 1):
g = [0] * (goal + 1)
for j in range(1, n + 1):
g[j] = f[j - 1] * (n - j + 1)
if j > k:
g[j] += f[j] * (j - k)
g[j] %= mod
f = g
return f[n]
Java
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
final int mod = (int) 1e9 + 7;
long[] f = new long[n + 1];
f[0] = 1;
for (int i = 1; i <= goal; ++i) {
long[] g = new long[n + 1];
for (int j = 1; j <= n; ++j) {
g[j] = f[j - 1] * (n - j + 1);
if (j > k) {
g[j] += f[j] * (j - k);
}
g[j] %= mod;
}
f = g;
}
return (int) f[n];
}
}
C++
class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
const int mod = 1e9 + 7;
vector<long long> f(n + 1);
f[0] = 1;
for (int i = 1; i <= goal; ++i) {
vector<long long> g(n + 1);
for (int j = 1; j <= n; ++j) {
g[j] = f[j - 1] * (n - j + 1);
if (j > k) {
g[j] += f[j] * (j - k);
}
g[j] %= mod;
}
f = move(g);
}
return f[n];
}
};
Go
func numMusicPlaylists(n int, goal int, k int) int {
const mod = 1e9 + 7
f := make([]int, goal+1)
f[0] = 1
for i := 1; i <= goal; i++ {
g := make([]int, goal+1)
for j := 1; j <= n; j++ {
g[j] = f[j-1] * (n - j + 1)
if j > k {
g[j] += f[j] * (j - k)
}
g[j] %= mod
}
f = g
}
return f[n]
}
TypeScript
function numMusicPlaylists(n: number, goal: number, k: number): number {
const mod = 1e9 + 7;
let f = new Array(goal + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= goal; ++i) {
const g = new Array(goal + 1).fill(0);
for (let j = 1; j <= n; ++j) {
g[j] = f[j - 1] * (n - j + 1);
if (j > k) {
g[j] += f[j] * (j - k);
}
g[j] %= mod;
}
f = g;
}
return f[n];
}