1259. 不相交的握手 動態規劃

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)