aboutsummaryrefslogtreecommitdiff
path: root/other/num_music_playlists.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/num_music_playlists.cpp')
-rw-r--r--other/num_music_playlists.cpp40
1 files changed, 40 insertions, 0 deletions
diff --git a/other/num_music_playlists.cpp b/other/num_music_playlists.cpp
new file mode 100644
index 0000000..78cad3c
--- /dev/null
+++ b/other/num_music_playlists.cpp
@@ -0,0 +1,40 @@
+// 920. Number of Music Playlists
+#include "leetcode.h"
+
+/*
+ * 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:
+ * - every song is played at least once
+ * - a song can only be played again only if 'k' other songs have been played
+ * given 'n, goal, k', return the number of possible playlists that you can
+ * create. since the answer can be very large, return it modulo 10^9+7
+ */
+
+class Solution {
+ const int mod = 1e9 + 7;
+ long long solve(int n, int goal, int k, vvd & dp) {
+ if (!n && !goal)
+ return 1;
+ if (!n || !goal)
+ return 0;
+ if (dp[n][goal] != -1)
+ return dp[n][goal];
+ long long pick = solve(n - 1, goal - 1, k, dp) * n;
+ long long skip = solve(n, goal - 1, k, dp) * max(n - k, 0);
+ return dp[n][goal] = (pick + skip) % mod;
+ }
+
+public:
+ int numMusicPlaylists(int n, int goal, int k) {
+ vvd dp(n + 1, vector<int>(goal + 1, -1));
+ return solve(n, goal, k, dp);
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.numMusicPlaylists(3, 3, 1)); // expect: 6
+ printf("%d\n", obj.numMusicPlaylists(2, 3, 0)); // expect: 6
+ printf("%d\n", obj.numMusicPlaylists(2, 3, 1)); // expect: 2
+}