資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中不會交叉的握手
假設我們有偶數個人 n 站在一個圓圈周圍，每個人都與其他人握手，總共有 n / 2 次握手。我們必須找到這些握手可能發生的方式數量，這樣就不會有任何握手交叉。答案可能非常大，因此返回答案模 10^9 + 7。
因此，如果輸入類似於 n = 2，則輸出將為 1
為了解決這個問題，我們將遵循以下步驟：
m := 10^9 + 7
定義一個大小為 (n+1) 的陣列 dp
dp[0] := 1
初始化 i := 0，當 i <= n 時，更新 i := i + 2，執行：
初始化 j := 0，當 j <= i-2 時，更新 j := j + 2，執行：
dp[i] := dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)
dp[i] := dp[i] mod m
返回 dp[n] mod m
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9+7;
typedef long long int lli;
class Solution {
public:
int numberOfWays(int n) {
vector <lli> dp(n+1);
dp[0] = 1;
for(int i = 0; i <= n; i+=2 ){
for(int j =0 ; j <= i-2; j+=2){
dp[i] += (dp[j]%m * dp[i-2-j]%m)%m;
dp[i]%=m;
}
}
return dp[n]%m;
}
};
main(){
Solution ob;
cout << (ob.numberOfWays(2));
}輸入
2
輸出
1
更新於：2020年7月11日
267 次檢視
廣告