Skip to content

Latest commit

 

History

History
216 lines (168 loc) · 5.25 KB

File metadata and controls

216 lines (168 loc) · 5.25 KB
comments difficulty edit_url rating source tags
true
困难
1951
第 13 场双周赛 Q4
数学
动态规划

English Version

题目描述

偶数 个人站成一个圆,总人数为 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

解法

方法一:记忆化搜索

我们设计一个函数 $dfs(i)$,表示 $i$ 个人的握手方案数。答案为 $dfs(n)$

函数 $dfs(i)$ 的执行逻辑如下:

  • 如果 $i \lt 2$,那么只有一种握手方案,即不握手,返回 $1$
  • 否则,我们可以枚举第一个人与谁握手,记剩余的左边的人数为 $l$,右边的人数为 $r=i-l-2$,那么有 $dfs(i)= \sum_{l=0}^{i-1} dfs(l) \times dfs(r)$

为了避免重复计算,我们使用记忆化搜索的方法。

时间复杂度 $O(n^2)$,空间复杂度 $O(n)$。其中 $n$$numPeople$ 的大小。

Python3

class Solution:
    def numberOfWays(self, numPeople: int) -> int:
        @cache
        def dfs(i: int) -> int:
            if i < 2:
                return 1
            ans = 0
            for l in range(0, i, 2):
                r = i - l - 2
                ans += dfs(l) * dfs(r)
                ans %= mod
            return ans

        mod = 10**9 + 7
        return dfs(numPeople)

Java

class Solution {
    private int[] f;
    private final int mod = (int) 1e9 + 7;

    public int numberOfWays(int numPeople) {
        f = new int[numPeople + 1];
        return dfs(numPeople);
    }

    private int dfs(int i) {
        if (i < 2) {
            return 1;
        }
        if (f[i] != 0) {
            return f[i];
        }
        for (int l = 0; l < i; l += 2) {
            int r = i - l - 2;
            f[i] = (int) ((f[i] + (1L * dfs(l) * dfs(r) % mod)) % mod);
        }
        return f[i];
    }
}

C++

class Solution {
public:
    int numberOfWays(int numPeople) {
        const int mod = 1e9 + 7;
        int f[numPeople + 1];
        memset(f, 0, sizeof(f));
        function<int(int)> dfs = [&](int i) {
            if (i < 2) {
                return 1;
            }
            if (f[i]) {
                return f[i];
            }
            for (int l = 0; l < i; l += 2) {
                int r = i - l - 2;
                f[i] = (f[i] + 1LL * dfs(l) * dfs(r) % mod) % mod;
            }
            return f[i];
        };
        return dfs(numPeople);
    }
};

Go

func numberOfWays(numPeople int) int {
	const mod int = 1e9 + 7
	f := make([]int, numPeople+1)
	var dfs func(int) int
	dfs = func(i int) int {
		if i < 2 {
			return 1
		}
		if f[i] != 0 {
			return f[i]
		}
		for l := 0; l < i; l += 2 {
			r := i - l - 2
			f[i] = (f[i] + dfs(l)*dfs(r)) % mod
		}
		return f[i]
	}
	return dfs(numPeople)
}

TypeScript

function numberOfWays(numPeople: number): number {
    const mod = 10 ** 9 + 7;
    const f: number[] = Array(numPeople + 1).fill(0);
    const dfs = (i: number): number => {
        if (i < 2) {
            return 1;
        }
        if (f[i] !== 0) {
            return f[i];
        }
        for (let l = 0; l < i; l += 2) {
            const r = i - l - 2;
            f[i] += Number((BigInt(dfs(l)) * BigInt(dfs(r))) % BigInt(mod));
            f[i] %= mod;
        }
        return f[i];
    };
    return dfs(numPeople);
}