當前位置:網站首頁>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

做題結果

成功,這題大概屬於困難題中特別簡單的

方法:動態規劃

  1. 假設有 x 個人,我們從中任選了一個人 a,這個 a和一個人握手,要保證後續有解,則分割出的兩部分必須都為偶數
  2. a 握手以後,還剩下,x-2個人沒握手,x 握手以後,把剩餘人員通過握手的連線分割為兩部分,假設其中一個部分為 y 個人,則剩餘部分為 x-2-y 個人
  3. 這個 y 人握手問題,就化解為了 x 人握手的子問題,枚舉 所有可行的 y 和 x-2-y 握手可能性,兩者互不幹涉,可相乘處理

優化

  1. 由於都是偶數,我們只關心有多少對握手,可將空間範圍縮减為 n/2
  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

隨機推薦