Number Of Music Playlists Problem


Description

LeetCode Problem 920.

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 10^9 + 7.

Example 1:

1
2
3
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:

1
2
3
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:

1
2
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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    // F(N,L,K) = F(N - 1, L - 1, K) * N + F(N, L - 1, K) * (N - K)
    // For F(N - 1, L - 1, K), if only N - 1 in the L - 1 first songs.
    // We need to put the rest one at the end of music list.
    // Any song can be this last song, so there are N possible combinations.
    // For F(N, L - 1, K), if already N in the L - 1 first songs.
    // We can put any song at the end of music list, 
    // but it should be different from K last song. We have N - K choices.
    int numMusicPlaylists(int N, int L, int K) {
        long dp[N + 1][L + 1], mod = 1e9 + 7;
        for (int i = K + 1; i <= N; ++i)
            for (int j = i; j <= L; ++j)
                if ((i == j) || (i == K + 1))
                    dp[i][j] = factorial(i);
                else
                    dp[i][j] = (dp[i - 1][j - 1] * i + dp[i][j - 1] * (i - K)) % mod;
        return (int) dp[N][L];
    }

    long factorial(int n) {
        return n ? factorial(n - 1) * n % (long)(1e9 + 7) : 1;
    }
};




Related Posts

Valid Permutations For DI Sequence Problem

LeetCode 903. You are given a string s of length...

Tallest Billboard Problem

LeetCode 956. You are installing a billboard and want it...

Sum Of Subarray Minimums Problem

LeetCode 907. Given an array of integers arr, find the...

Stone Game Problem

LeetCode 877. Alice and Bob play a game with piles...

Split Array With Same Average Problem

LeetCode 805. You are given an integer array nums.

Soup Servings Problem

LeetCode 808. There are two types of soup, type A...