播放列表的数量

难度: Hard

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

每首歌 至少播放一次 。
一首歌只有在其他 k 首歌播放完之后才能再次播放。

给你 n、goal 和 k ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 10⁹ + 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

Submission

运行时间: 33 ms

内存: 16.0 MB

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 range(2, N-K+1):
            for i in range(1, L-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)

Explain

题解使用动态规划的方法，考虑dp数组存储在选择了P首歌曲，已经播放了S首不同的歌曲的情况下的播放列表数量。初始化dp数组为长度L-N+1，其中dp[i]表示选择了i+S首歌的所有可能的播放列表数量。然后通过两层循环，外层循环从2至N-K+1，内层从1至L-N+1，使用状态转移更新dp数组，最后将计算的结果乘以N的阶乘，以包括所有可能的不同歌曲的排列组合，最后结果取模10^9+7。

时间复杂度: O((N-K)*(L-N) + N)

空间复杂度: O(L-N+1)

class Solution(object):
    def numMusicPlaylists(self, N, L, K):
        # dp数组初始化，dp[i]代表选择了i+N首歌的播放列表数量
        dp = [1] * (L-N+1)
        # 外层循环控制已选不同歌曲的数量
        for p in range(2, N-K+1):
            # 内层循环通过前一个状态计算当前状态的播放列表数量
            for i in range(1, L-N+1):
                dp[i] += dp[i-1] * p

        # 通过计算N的阶乘并乘以dp数组最后一个元素来得到最终答案
        ans = dp[-1]
        for k in range(2, N+1):
            ans *= k
        # 返回结果对10^9+7取模
        return ans % (10**9 + 7)

Explore

动态规划数组dp[i]的定义是关键于解决问题的核心。在这个问题中，dp[i]代表选择了i+N首歌曲的所有可能的播放列表数量。这里的i表示超过N的额外歌曲数，所以i+N就是目前列表中的总歌曲数。正确理解dp[i]的定义帮助我们构建状态转移方程，将问题从一个规模转移到更大的规模，最终解决整个问题。在应用中，我们从最基本的情况开始，逐步通过已知的状态推算出未知的状态。

初始化dp数组所有元素为1是基于特定的前提条件，即至少有一种方式构建播放列表（即选择N首不同的歌曲，每首歌恰好播放一次）。因此，这种初始化适用于当L（播放列表长度）大于等于N（不同歌曲的数量）的情况。如果L小于N，这样的初始化就不再适用，因为不可能在播放列表长度小于歌曲总数的情况下满足每首歌至少播放一次的条件。

状态转移方程的设计考虑了每首歌至少播放一次和每首新歌之间至少有K首其他歌曲的间隔规则。动态规划的每一步代表在当前已选歌曲的基础上，增加新的不同的歌曲到播放列表中。每增加一首新歌，都基于前一个状态（较少的歌曲数），考虑新增歌曲的各种放置位置和可能性，从而更新当前的状态。这种递推关系直接反映了每首新歌引入的变化以及如何从已有的播放列表状态转移到新的状态。

将dp数组的最终结果乘以N的阶乘是为了考虑不同歌曲的所有可能排列。dp数组计算的是在满足特定条件下的播放列表数目，不考虑歌曲的具体排列顺序。N的阶乘是用来计算N首不同歌曲的所有可能顺序，这样我们就能得到所有合法的播放列表，确保每种歌曲的排列都被计算在内。这是因为dp数组在计算时仅考虑了歌曲数目的增加，而没有具体到每一首歌的排列顺序。