920. Number of Music Playlists

Difficulty:
Related Topics:
Similar Questions:

Problem

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:

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:

Solution

/**
 * @param {number} n
 * @param {number} goal
 * @param {number} k
 * @return {number}
 */
var numMusicPlaylists = function(n, goal, k) {
    var mod = Math.pow(10, 9) + 7;
    var dp = Array(goal + 1).fill(0).map(() => Array(n + 1).fill(0));
    dp[0][0] = 1;
    for (var i = 1; i <= goal; i++) {
        for (var j = 1; j <= Math.min(i, n); j++) {
            // new song
            dp[i][j] = dp[i - 1][j - 1] * (n - (j - 1)) % mod;
            // old song
            if (j > k) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % mod;
            }
        }
    }
    return dp[goal][n];
};

Explain:

Bottom-up DP.

Complexity: