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
2MOD = 10**9 + 7
3def numMusicPlaylists(n, goal, k):
4 dp = [[0] * (goal + 1) for _ in range(n + 1)]
5 dp[0][0] = 1
6 for i in range(1, n + 1):
7 for j in range(1, goal + 1):
8 dp[i][j] = dp[i - 1][j - 1] * (n - i + 1) % MOD
9 if i > k:
10 dp[i][j] += dp[i][j - 1] * (i - k) % MOD
11 dp[i][j] %= MOD
12 return dp[n][goal]
13The solution uses a 2D list to store the number of ways to create a playlist of length j with i distinct songs. The state transition involves adding a new song or reusing one respecting the separation condition. The final solution is found at dp[n][goal].
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.