Algorithm
Problem Name: 920. Number of Music Playlists
Problem Link: https://leetcode.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
kother 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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int numMusicPlaylists(int N, int L, int K){
long *dp;
int i, j, x;
// dp[i][j]: number of possible answers on listening to i with j songs
// then we want to get dp[L][N]
dp = calloc((L + 1) * (N + 1), sizeof(*dp));
//assert(dp);
#define IDX(I, J) ((I) * (N + 1) + (J))
dp[IDX(0, 0)] = 1;
for (i = 1; i < = L; i ++) {
for (j = 1; j < = N; j ++) {
x = N - j + 1; // number of songs not being selected (including current song j)
dp[IDX(i, j)] = dp[IDX(i - 1, j - 1)] * x; // choose a new song
x = j - K; // number of played songs (including song j) can be re-selected
if (x > 0) {
dp[IDX(i, j)] += dp[IDX(i - 1, j)] * x; // choose a played songs
}
dp[IDX(i, j)] %= 1000000007;
}
}
i = dp[IDX(L, N)];
free(dp);
return i;
}
Input
n = 3, goal = 3, k = 1
Output
6
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numMusicPlaylists = function (N, L, K) {
const mod = 10 ** 9 + 7
const dp = Array.from({ length: L + 1 }, () => Array(N + 1).fill(0))
dp[0][0] = 1
for (let i = 1; i < = L; i++) {
for (let j = 1; j < = N; j++) {
dp[i][j] = (dp[i - 1][j - 1] * (N - (j - 1))) % mod
if (j > K) {
dp[i][j] = (dp[i][j] + ((dp[i - 1][j] * (j - K)) % mod)) % mod
}
}
}
return dp[L][N]
}
Input
n = 3, goal = 3, k = 1
Output
6
#3 Code Example with Python Programming
Code -
Python Programming
from functools import lru_cache
class Solution:
def numMusicPlaylists(self, N, L, K):
@lru_cache(None)
def dp(i, j): return +(j == 0) if not i else (dp(i-1, j-1) * (N-j+1) + dp(i-1, j) * max(j-K, 0)) % (10**9+7)
return dp(L, N)
Input
n = 2, goal = 3, k = 0
Output
6