What is the primary algorithmic pattern used to solve the Number of Music Playlists problem?

The primary pattern used is state transition dynamic programming, where the problem is broken into smaller subproblems and solved recursively.

How do you ensure the result is within limits for large numbers in this problem?

We use modular arithmetic with modulo 10^9 + 7 to prevent overflow and keep the numbers manageable during the computation process.

Why is combinatorics important in solving the Number of Music Playlists problem?

Combinatorics helps count how songs are added or repeated in the playlist, respecting the constraint on consecutive repetitions of songs.

How can dynamic programming be optimized in this problem?

The dynamic programming table can be optimized by reducing space complexity to O(n) by only storing the states for the current number of distinct songs used.

What edge cases should be considered for the Number of Music Playlists problem?

Consider edge cases such as when k = 0, where no song can repeat, or when n = goal, where the playlist must use every song exactly once.

#920

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

播放列表的数量

你的音乐播放器里有 n 首不同的歌，在旅途中，你计划听 goal 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：每首歌至少播放一次。一首歌只有在其他 k 首歌播放完之后才能再次播放。给你 n 、 goal 和 k ，返回可以满足要求的播放列表的数量。由于答案可能非常大…

数学动态规划组合数学

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们定义 $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$ 为题目中给定的参数。

1

2

3

4

5

6

7

8

9

10

11

12

13

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]

speed

复杂度分析

指标	值
时间	O(n \log \text{goal})
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of dynamic programming and modular arithmetic.
question_mark
The candidate can clearly explain the logic behind state transitions and playlist constraints.
question_mark
The candidate is able to optimize a combinatorial counting problem using dynamic programming techniques.

warning

常见陷阱

外企场景

error
Misunderstanding the modular arithmetic and failing to apply modulo 10^9 + 7 correctly.
error
Incorrectly handling the case where no songs can be repeated within k songs, especially when constructing the DP table.
error
Overlooking the fact that playlist lengths must exactly equal goal, which can lead to edge case errors when calculating the result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling larger values of n and goal, which increases the complexity of the state transitions and the time required to compute the result.
arrow_right_alt
Adapting the problem to include additional constraints such as a maximum number of distinct songs in the playlist.
arrow_right_alt
Solving the problem in a distributed manner where the DP states can be computed concurrently.

help

常见问题

外企场景

继续练习

#1359 有效的快递序列数目 #458 可怜的小猪 #1467 两个盒子中球的颜色数相同的概率