資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中音樂播放列表的數量
假設我們有一個音樂播放器，其中包含 N 首不同的歌曲，我們想在旅途中收聽 L 首歌曲。因此，我們必須製作一個播放列表，以滿足以下條件：
每首歌曲至少播放一次
一首歌曲只有在播放了 K 首其他歌曲後才能再次播放。
我們必須找到可能的播放列表的數量。答案可能非常大，因此我們將返回它對 10^9 + 7 取模的結果。
因此，如果輸入類似於 N = 2，L = 3，K = 0，則輸出將為 6，因為有 6 個可能的播放列表：[1,1,2]，[1,2,1]，[2,1,1]，[2,2,1]，[2,1,2]，[1,2,2]。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 add()，它將接收 a、b，
返回 ((a mod m) + (b mod m)) mod m
定義一個函式 sub()，它將接收 a、b，
返回 ((a mod m) - (b mod m) + m) mod m
定義一個函式 mul()，它將接收 a、b，
返回 ((a mod m) * (b mod m)) mod m
在主方法中，執行以下操作：
建立一個大小為 dp(L + 1) x (N + 1) 的二維陣列
dp[0, 0] := 1
對於初始化 i := 1，當 i <= L 時，更新（i 增加 1），執行：
對於初始化 j := 1，當 j <= N 時，更新（j 增加 1），執行：
dp[i, j] := mul(dp[i - 1, j - 1], (N - (j - 1)))
如果 j > K，則：
dp[i, j] := add(dp[i, j], mul(dp[i - 1, j], j - K))
返回 dp[L, N]
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
int add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int sub(lli a, lli b){
return ((a % m) - (b % m) + m) % m;
}
int mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
int numMusicPlaylists(int N, int L, int K) {
vector < vector <int> > dp(L + 1, vector <int>(N + 1));
dp[0][0] = 1;
for(int i = 1; i <= L; i++){
for(int j = 1; j <= N; j++){
dp[i][j] = mul(dp[i - 1][j - 1], (N - (j - 1)));
if(j > K){
dp[i][j] = add(dp[i][j], mul(dp[i - 1][j], j -
K));
}
}
}
return dp[L][N];
}
};
main(){
Solution ob;
cout << (ob.numMusicPlaylists(2, 3, 0));
}輸入
2,3,0
輸出
6
更新於：2020年6月4日
426 次瀏覽
廣告