原文链接: https://leetcode-cn.com/problems/number-of-music-playlists

英文原文

Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:

• Every song is played at least once.
• A song can only be played again only if k other songs have been played.

Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

Example 2:

Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].

Example 3:

Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

 

Constraints:

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

中文题目

你的音乐播放器里有 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]

 

提示：

1. 0 <= K < N <= L <= 100

通过代码

官方题解

方法 1：动态规划

想法

令 dp[i][j] 为播放列表长度为 i 包含恰好 j 首不同歌曲的数量。我们需要计算 dp[L][N]，看上去可以通过 dp 来解决。

算法

考虑 dp[i][j]。最后一首歌，我们可以播放没有播放过的歌也可以是播放过的。如果未播放过的，那么就是 dp[i-1][j-1] * (N-j) 种选择方法。如果不是，那么就是选择之前的一首歌，dp[i-1][j] * max(j-K, 0)（j 首歌，最近的 K 首不可以播放）。

[]
class Solution {
    public int numMusicPlaylists(int N, int L, int K) {
        int MOD = 1_000_000_007;

        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];
    }
}

[]
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)

复杂度分析

• 时间复杂度：$O(NL)$。
• 空间复杂度：$O(NL)$。（然而，我们可以只存储最后一列的 dp 数组来优化空间，这样只需要 $O(L)$ 的空间复杂度。）

方法 2：分类 + 动态规划

（注意：这个方法相当具有挑战性，但是在模拟这种列表时是一个常见的结论）

想法

由于我们只关心播放次数至少一次的歌，我们记录每首歌第一次播放的时刻 $x = (x_1, x_2, \cdots)$。例如，我们有 5 首歌 abcde，播放列表为 abacabdcbaeacbd，那么 $x = (1, 2, 4, 7, 11)$ 就是第一首歌出现的时刻。方便起见，我们让 $x_{N+1} = L+1$。我们的策略就是计算满足 $x$ 的播放列表个数 $#_x$，最后结果是 $\sum #_x$。

直接计算，

$$
#x = N * (N-1) * \cdots * (N-K+1) 1^{x{K+1} - x_K - 1} * (N-K+2) 2^{x_{K+2} - x_{K+1}} * \cdots
$$

$$
\Rightarrow #x = N! \prod{j=1}^{N-K+1} j^{x_{K+j} - x_{K+j-1} - 1}
$$

令 $\delta_i = x_{K+i} - x_{K+i-1} - 1$，所以 $\sum \delta_i = L-N$。所以最后结果是（$S = L-N, P = N-K+1$）：

$$
N! \Big(\sum\limits_{\delta : \sum\limits_{0 \leq i \leq P} \delta_i = S} \prod\limits_{j=1}^P j^{\delta_j} \Big)
$$

方便起见,将这个结果记录为 $\langle S, P\rangle$。

算法

我们可以通过数学方法迭代计算 $\langle S, P\rangle$ 的值，通过提出因子 $P^{\delta_P}$。

$$
\langle S, P\rangle = \sum_{\delta_P = 0}^S P^{\delta_P} \sum_{\sum\limits_{0\leq i < P} \delta_i = S - \delta_P} \prod\limits_{j=1}^{P-1} j^{\delta_j}
$$

$$
\Rightarrow \langle S, P\rangle = \sum_{\delta_P = 0}^S P^{\delta_P} \langle S - \delta_P, P-1\rangle
$$

所以可以写成代数形式：

$$
\langle S, P \rangle = P \langle S-1, P-1 \rangle + \langle S, P-1 \rangle
$$

通过这个迭代，我们可以通过类似方法 1 使用动态规划算法。最后的结果是 $N! \langle L-N, N-K+1 \rangle$。

[]
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;
    }
}

[]
class Solution(object):
    def numMusicPlaylists(self, N, L, K):
        # dp[S] at time P = <S, P> as discussed in article
        dp = [1] * (L-N+1)
        for p in xrange(2, N-K+1):
            for i in xrange(1, L-N+1):
                dp[i] += dp[i-1] * p

        # Multiply by N!
        ans = dp[-1]
        for k in xrange(2, N+1):
            ans *= k
        return ans % (10**9 + 7)

复杂度分析

• 时间复杂度：$O(NL)$。
• 空间复杂度：$O(L)$。

方法 3：生成函数

（注意：这个解法非常难，同时不推荐在面试中使用，但为了题解的完整性实现于此。）

分析

按照方法 2 的术语，我们希望快速计算 $\langle S, P \rangle$。我们使用生成函数。

对于一个固定的 $P$，考虑函数：

$$
f(x) = (1^0x^0 + 1^1x^1 + 1^2x^2 + 1^3x^3 + \cdots) * (2^0x^0 + 2^1x^1 + 2^2x^2 + 2^3x^3 + \cdots)
$$
$$
\cdots * (P^0x^0 + P^1x^1 + P^2x^2 + P^3x^3 + \cdots)
$$

$$
\Leftrightarrow f(x) = \prod_{k=1}^{P} (\sum_{j \geq 0} k^j x^j) = \prod_{k=1}^P \frac{1}{1-kx}
$$

$f$ 中 $x^S$ 的系数（记为 $[x^S]f$）就是 $\langle S, P \rangle$。

根据中国剩余定理，这个乘积可以写成一个部分分数的形式：

$$
\prod_{k=1}^P \frac{1}{1-kx} = \sum_{k=1}^P \frac{A_k}{1-kx}
$$

对于一些有理系数 $A_k$。我们也可以通过清除分母并对 $1 \leq m \leq P$ 设 $x = 1/m$，根据每个给定的 $m$，所有的元素项除了第 $m$ 项会消失，有：

$$
A_m = \frac{1}{\prod_{1 \leq j \leq P & j \neq m} 1 - j/m} = \prod_{j \neq m} \frac{m}{m-j}
$$

由于 $\sum_{j \geq 0} (kx)^j = \frac{1}{1-kx}$，所以合在一起有：

$$
[x^S]f = \sum_{k=1}^P A_k * k^S
$$

所以最终结果为

$$
\text{answer} = N! \sum_{k=1}^{N-K} k^{L-N} \prod_{1 \leq j \leq N-K & j \neq k} \frac{k}{k-j}
$$

$$
\Rightarrow \text{answer} = N! \sum_k k^{L-K-1} \prod_{j \neq k} \frac{1}{k-j}
$$

我们只需要一个快速的方法计算 $C_k = \prod_{j \neq k} \frac{1}{k-j}$，事实上，

$$
C_{k+1} = C_k * \frac{k - (N-K)}{k}
$$

所以我们就有了所有计算的表达式。

[]
class Solution(object):
    def numMusicPlaylists(self, N, L, K):
        MOD = 10**9 + 7
        def inv(x):
            return pow(x, MOD-2, MOD)

        C = 1
        for x in xrange(1, N-K):
            C *= -x
            C %= MOD
        C = inv(C)

        ans = 0
        for k in xrange(1, N-K+1):
            ans += pow(k, L-K-1, MOD) * C
            C = C * (k - (N-K)) % MOD * inv(k) % MOD

        for k in xrange(1, N+1):
            ans = ans * k % MOD
        return ans

复杂度分析

• 时间复杂度：$O(N \log L)$。
• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
1971	4064	48.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言