1259. 不相交的握手 - Kotlin 动态规划 一维DP

Problem: 1259. 不相交的握手

思路

设是n个人握手时的可能性，我们令i从0遍历到numPeople

考虑i个人握手的情况，当第i个人（最后一个人）与第k个人握手（从1起始）时，假设所有人站成一圈，则此时i和k之间的连线将所有人分为k-1和i-k-1两部分，此时握手的组合数即为k-1个人握手和i-k-1个人握手的组合数之积

考虑到只有偶数个人可以握手，因此被i和k划分开的两组人也必须为偶数，显而易见i必然为偶数，则k必须为奇数才能将其余部分划分为两组偶数个人

对于i个人握手的所有可能性，令奇数k遍历1到i-1，将所有的组合数相加即为的结果

考虑边界情况：当i与第1个人或第i-1个人握手时，此时人群被分为i-2个人和0个人，显而易见此时的组合数为i-2个人握手的情况，由于结果是两组人的组合数之积，因此

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun numberOfWays(numPeople: Int): Int {
        val dp = LongArray(numPeople + 1) { i: Int -> if (i == 0 || i == 2) 1 else 0 }
        for (i in 4..numPeople step 2) {
            for (k in 1..i step 2) {
                dp[i] = (dp[i] + dp[k - 1] * dp[i - k - 1]) % 1000000007
            }
        }
        return (dp[numPeople] % 1000000007).toInt()
    }
}