當前位置:網站首頁>1259. 不相交的握手 動態規劃
1259. 不相交的握手 動態規劃
2022-07-23 18:41:28【鈺娘娘】
1259. 不相交的握手
偶數 個人站成一個圓,總人數為
num_people
。每個人與除自己外的一個人握手,所以總共會有num_people / 2
次握手。將握手的人之間連線,請你返回連線不會相交的握手方案數。
由於結果可能會很大,請你返回答案 模
10^9+7
後的結果。示例 1:
輸入:num_people = 2 輸出:1示例 2:
輸入:num_people = 4 輸出:2 解釋:總共有兩種方案,第一種方案是 [(1,2),(3,4)] ,第二種方案是 [(2,3),(4,1)] 。示例 3:
輸入:num_people = 6 輸出:5示例 4:
輸入:num_people = 8 輸出:14提示:
2 <= num_people <= 1000
num_people % 2 == 0
做題結果
成功,這題大概屬於困難題中特別簡單的
方法:動態規劃
- 假設有 x 個人,我們從中任選了一個人 a,這個 a和一個人握手,要保證後續有解,則分割出的兩部分必須都為偶數
- a 握手以後,還剩下,x-2個人沒握手,x 握手以後,把剩餘人員通過握手的連線分割為兩部分,假設其中一個部分為 y 個人,則剩餘部分為 x-2-y 個人
- 這個 y 人握手問題,就化解為了 x 人握手的子問題,枚舉 所有可行的 y 和 x-2-y 握手可能性,兩者互不幹涉,可相乘處理
優化
- 由於都是偶數,我們只關心有多少對握手,可將空間範圍縮减為 n/2
- 一邊分割為 y 人,一邊分割為 x-2-y 人,與反過來的結果是相同的,那麼對於兩邊數目不同的情况,可以乘以2,從而减少一半循環次數,特別注意的是,當 y=x-2-y時,只有一種可能性,
class Solution {
public int numberOfWays(int numPeople) {
int half = numPeople/2;
long[] dp = new long[half+1];
long MOD = (long) (1e9+7);
dp[0]=1;
for(int i = 1; i <= half; i++){
for(int j = 0; j < i-j-1; j++){
dp[i]+=dp[j]*dp[i-j-1]*2;
dp[i] = dp[i]%MOD;
}
if(i%2!=0){
dp[i]+=dp[i/2]*dp[i-i/2-1];
dp[i] = dp[i]%MOD;
}
}
return (int) dp[half];
}
}
時間複雜度:O(n)
空間複雜度:O(n)
版權聲明
本文為[鈺娘娘]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207231633280728.html
邊欄推薦
猜你喜歡
隨機推薦
- BGP機房的優點
- 真人踩過的坑,告訴你避免自動化測試常犯的10個錯誤
- 判斷是否為void類型
- C語言——幾道C語言經典習題
- openvino_datawhale
- C語言基礎知識梳理(一)
- Redis源碼與設計剖析 -- 7.快速列錶
- 比特,比特,字節,字的概念與區別
- 項目部署(簡版)
- JDBC的學習以及簡單封裝
- [pytho-flask筆記5]藍圖簡單使用
- Web Component-自定義元素的生命周期
- 數倉4.0筆記——業務數據采集
- 數倉4.0筆記——用戶行為數據采集四
- 對.h5文件的迭代顯示,h5py數據操作
- 常用數學知識匯總
- “東數西算”下數據中心的液冷GPU服務器如何發展?
- 硬件知識1--原理圖和接口類型(基於百問網硬件操作大全視頻教程)
- 鋼結構基本原理複習
- Unity3d:UGUI源碼,Rebuild優化
- 快速解决:Xshell拖不進去文件夾或者軟件包的問題
- RHCSA--文件內容瀏覽、cut、uniq、sort、.tr命令使用
- 信號完整性(SI)電源完整性(PI)學習筆記(三十二)電源分配網路(四)
- EasyGBS平臺出現錄像無法播放並存在RTMP重複推流現象,是什麼原因?
- 第七天筆記
- 【可視化調度軟件】上海道寧為SMB組織帶來NETRONIC下載、試用、教程
- 概率沉思錄:2.The quantitative rules
- 常用的鼠標事件和鍵盤事件
- C#:in、out、ref關鍵字
- GRE,MGRE的詳細了解;OSPF基礎配置知識
- Creo 9.0 如何快速修改CAD坐標系?
- 第五天筆記
- 强化學習——策略梯度理解點
- shell跑的時候需要的需要了解命令
- OKRK3399開發板預留I2C4掛載EEPROM
- 優化華為雲服務器采用Key登陸
- 第2章 基礎查詢與排序
- 【C語言】猜數字小遊戲+關機小程序
- 什麼是Per-Title編碼?
- @FeignClient使用詳細教程(圖解)