Number of Music Playlists

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:

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

Solution:

Finally, I was able to peel it off with these baby steps:



Finally, the count of playlists with all restrictions is: [1] - sum([2] * [3] for[1..N-1])


class Solution {
    int mod = (int) 1e9 + 7;
    
    private int[][] comb(int n) {
        int[][] comb = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i ++) {
            for (int j = 0; j <= i; j ++) {
                if (j == 0 || i == j) {
                    comb[i][j] = 1;
                } else {
                    comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
                }
            }
        }
        return comb;
    }
    
    Long[][] dp;
    
    public int numMusicPlaylists(int N, int L, int K) {
        dp = new Long[N + 1][L + 1];
        return (int) (helper(N, L, K, comb(N)) % mod);
    }
    
    private long helper(int N, int L, int K, int[][] comb) {
        if (K > N) return 0;
        if (dp[N][L] != null) return dp[N][L];
        long total = 1;
        for (int i = 0; i < L; i ++) {
            total = (total * (N - Math.min(i, K))) % mod;
        }
        for (int i = 1; i < N; i ++) {
            total = (total - (comb[N][i] * helper(i, L, K, comb)) % mod + mod) % mod;
        }
        return dp[N][L] = total;
    }
}