diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/num_music_playlists.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/num_music_playlists.cpp')
-rw-r--r-- | other/num_music_playlists.cpp | 40 |
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 +} |