# 920. Number of Music Playlists     ## Approach 1: Top-down

• Time: $O(NL)$
• Space: $O(NL)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: int numMusicPlaylists(int n, int goal, int k) { this->n = n; this->k = k; // dp[i][j] := # of playlists with i songs and j different songs dp.resize(goal + 1, vector(n + 1, -1)); return playlists(goal, n); } private: static constexpr int kMod = 1'000'000'007; int n; int k; vector> dp; long playlists(int i, int j) { if (i == 0) return j == 0; if (j == 0) return 0; if (dp[i][j] >= 0) return dp[i][j]; dp[i][j] = playlists(i - 1, j - 1) * (n - (j - 1)); // Last song is new dp[i][j] += playlists(i - 1, j) * max(0, j - k); // Last song is old return dp[i][j] %= kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public int numMusicPlaylists(int n, int goal, int k) { this.n = n; this.k = k; // dp[i][j] := # of playlists with i songs and j different songs dp = new long[goal + 1][n + 1]; Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1)); return (int) playlists(goal, n); } private static final int kMod = 1_000_000_007; private int n; private int k; private long[][] dp; private long playlists(int i, int j) { if (i == 0) return j == 0 ? 1 : 0; if (j == 0) return 0; if (dp[i][j] >= 0) return dp[i][j]; dp[i][j] = playlists(i - 1, j - 1) * (n - (j - 1)); // Last song is new dp[i][j] += playlists(i - 1, j) * Math.max(0, j - k); // Last song is old return dp[i][j] %= kMod; } } 

## Approach 2: Bottom-up

• Time: $O(NL)$
• Space: $O(NL)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: int numMusicPlaylists(int n, int goal, int k) { constexpr int kMod = 1'000'000'007; // dp[i][j] := # of playlists with i songs and j different songs vector> dp(goal + 1, vector(n + 1)); dp = 1; for (int i = 1; i <= goal; ++i) for (int j = 1; j <= n; ++j) { dp[i][j] += dp[i - 1][j - 1] * (n - (j - 1)); // Last song is new dp[i][j] += dp[i - 1][j] * max(0, j - k); // Last song is old dp[i][j] %= kMod; } return dp[goal][n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int numMusicPlaylists(int n, int goal, int k) { final int kMod = 1_000_000_007; // dp[i][j] := # of playlists with i songs and j different songs long[][] dp = new long[goal + 1][n + 1]; dp = 1; for (int i = 1; i <= goal; ++i) for (int j = 1; j <= n; ++j) { dp[i][j] += dp[i - 1][j - 1] * (n - (j - 1)); // Last song is new dp[i][j] += dp[i - 1][j] * Math.max(0, j - k); // Last song is old dp[i][j] %= kMod; } return (int) dp[goal][n]; } }