Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/920.html

920. Number of Music Playlists (Hard)

Your music player contains N different songs and she wants to listen to L (not necessarily different) songs during your trip.  You 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

Return the number of possible playlists.  As the answer can be very large, return it modulo 10^9 + 7.

 

Example 1:

Input: N = 3, L = 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], [3, 2, 1].

Example 2:

Input: N = 2, L = 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], [1, 2, 2]

Example 3:

Input: N = 2, L = 3, K = 1
Output: 2
Explanation: There are 2 possible playlists. [1, 2, 1], [2, 1, 2]

 

Note:

  1. 0 <= K < N <= L <= 100

Related Topics:
Dynamic Programming

Solution 1. DP

Let dp[i][j] be the number of playlists of length i that have exactly j unique songs. The answer is dp[L][N].

To get dp[i][j], we consider the i-1-th song:

  • It has not been played before. This is the first time it’s played. The first i - 1 songs must have j - 1 unique songs. We can choose from N - (j - 1) new songs. So dp[i - 1][j - 1] * (N - j + 1) cases.
  • It has been played before. The first i - 1 songs must have j unique songs. This song is one of the j unique songs. The [i - K, i - 1] songs must be unique and the last song can’t be of these K songs. So we can only choose from the remaining j - K songs. dp[i - 1][j] * max(j - K, 0)
// OJ: https://leetcode.com/problems/number-of-music-playlists/
// Time: O(NL)
// Space: O(NL)
// Ref: https://leetcode.com/problems/number-of-music-playlists/solution/
class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        long dp[101][101] = {}, mod = 1e9+7;
        dp[0][0] = 1;
        for (int i = 1; i <= L; ++i) {
            for (int j = 1; j <= N; ++j) {
                dp[i][j] += dp[i - 1][j - 1] * (N - j + 1);
                dp[i][j] += dp[i - 1][j] * max(j - K, 0);
                dp[i][j] %= mod;
            }
        }
        return dp[L][N];
    }
};
  • class Solution {
        public int numMusicPlaylists(int N, int L, int K) {
            final int MODULO = 1000000007;
            long[][] dp = new long[L + 1][N + 1];
            dp[0][0] = 1;
            for (int i = 1; i <= L; i++) {
                for (int j = 1; j <= N; j++) {
                    dp[i][j] += dp[i - 1][j - 1] * (N - j + 1) + dp[i - 1][j] * Math.max(j - K, 0);
                    dp[i][j] %= MODULO;
                }
            }
            return (int) dp[L][N];
        }
    }
    
    ############
    
    class Solution {
        public int numMusicPlaylists(int n, int goal, int k) {
            final int mod = (int) 1e9 + 7;
            long[][] f = new long[goal + 1][n + 1];
            f[0][0] = 1;
            for (int i = 1; i <= goal; ++i) {
                for (int j = 1; j <= n; ++j) {
                    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 (int) f[goal][n];
        }
    }
    
  • // OJ: https://leetcode.com/problems/number-of-music-playlists/
    // Time: O(NL)
    // Space: O(NL)
    // Ref: https://leetcode.com/problems/number-of-music-playlists/solution/
    class Solution {
    public:
        int numMusicPlaylists(int N, int L, int K) {
            long dp[101][101] = {}, mod = 1e9+7;
            dp[0][0] = 1;
            for (int i = 1; i <= L; ++i) {
                for (int j = 1; j <= N; ++j) {
                    dp[i][j] += dp[i - 1][j - 1] * (N - j + 1);
                    dp[i][j] += dp[i - 1][j] * max(j - K, 0);
                    dp[i][j] %= mod;
                }
            }
            return dp[L][N];
        }
    };
    
  • 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]
    
    
  • func numMusicPlaylists(n int, goal int, k int) int {
    	const mod = 1e9 + 7
    	f := make([][]int, goal+1)
    	for i := range f {
    		f[i] = make([]int, n+1)
    	}
    	f[0][0] = 1
    	for i := 1; i <= goal; i++ {
    		for j := 1; j <= n; j++ {
    			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]
    }
    
  • function numMusicPlaylists(n: number, goal: number, k: number): number {
        const mod = 1e9 + 7;
        const f = new Array(goal + 1).fill(0).map(() => new Array(n + 1).fill(0));
        f[0][0] = 1;
        for (let i = 1; i <= goal; ++i) {
            for (let j = 1; j <= n; ++j) {
                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];
    }
    
    

All Problems

All Solutions