Sponsored
Sponsored
We define a dynamic programming approach where we use a 2D DP table where dp[i][j] means the number of ways to form a playlist of length j using i distinct songs. We will eventually find dp[n][goal].
The key recurrence relations are:
(n - i + 1) songs available, hence dp[i][j] += dp[i - 1][j - 1] * (n - i + 1)i songs, considering k songs must be between repeats, we have: dp[i][j] += dp[i][j - 1] * (i - k), where i > kThis draws from the constraints on repeats and expands the playlist iteratively.
Time Complexity: O(n * goal), since we iterate through each subproblem.
Space Complexity: O(n * goal), due to the size of the DP table.
1
2class Solution {
3 public int numMusicPlaylists(int n, int goal, int k) {
4 int MOD = 1000000007;
5 long[][] dp = new long[n + 1][goal + 1];
6 dp[0][0] = 1;
7 for (int i = 1; i <= n; ++i) {
8 for (int j = 1; j <= goal; ++j) {
9 dp[i][j] = dp[i - 1][j - 1] * (n - i + 1) % MOD;
10 if (i > k) {
11 dp[i][j] += dp[i][j - 1] * (i - k) % MOD;
12 }
13 dp[i][j] %= MOD;
14 }
15 }
16 return (int)dp[n][goal];
17 }
18}
19The Java solution mirrors the logic used in Python, employing a two-dimensional array to calculate the number of playlists that can be made.
This approach uses memoization to recursively compute the number of playlists. It calculates the playlists by considering whether a new song is added or an existing song is reused, accounting for k intervening songs.
Time Complexity: O(n * goal), due to memoization.
Space Complexity: O(n * goal), for memo storage.
1
2#include <vector>
3using namespace std;
4const int MOD = 1e9 + 7;
5vector<vector<int>> memo;
6
int totalPlaylists(int n, int goal, int k, int i, int j) {
if (j == 0) return i == 0 ? 1 : 0;
if (memo[i][j] != -1) return memo[i][j];
long res = (totalPlaylists(n, goal, k, i - 1, j - 1) * (n - i + 1)) % MOD;
if (i > k) {
res = (res + totalPlaylists(n, goal, k, i, j - 1) * (i - k)) % MOD;
}
return memo[i][j] = res;
}
int numMusicPlaylists(int n, int goal, int k) {
memo = vector<vector<int>>(n + 1, vector<int>(goal + 1, -1));
return totalPlaylists(n, goal, k, n, goal);
}
This C++ solution uses recursion with memoization to calculate the number of playlists. The function totalPlaylists recursively solves the problem by either adding new songs or reusing existing ones, with memoization avoiding redundant calculations.