Сложность: hard
В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 3, goal = 3, k = 1
Output: 6
👨💻 Алгоритм:
1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен.
2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)
3⃣Ответ находится в dp[goal][n].
😎 Решение:
def numMusicPlaylists(n, goal, k):
MOD = 10**9 + 7
dp = [[0] * (n + 1) for _ in range(goal + 1)]
dp[0][0] = 1
for i in range(1, goal + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
if j > k:
dp[i][j] += dp[i-1][j] * (j - k) % MOD
dp[i][j] %= MOD
return dp[goal][n]
Ставь 👍 и забирай 📚 Базу знаний