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)