字节笔试第二题思路

因此，dp[i] = sigma（dp[0...k] * dp[k+1...i]）

class Solution {
    public int numTrees(int n) {
        if(n < 0)
            return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n]; 
    }
}

回到本题：

将n个入口分别标记为1~n

同上思路n = 0时，结果为G(0)=1， n = 2时，结果也为G(2) =1，

n = 4时，所有的连接情况为（12,34）（14,23）,G(4) = 2，n = 6时，所有的连接情况为（12,34,56）（12,36,45）（14,23,56）（16,23,45）（16,25,34）,G(6) = 5。通过观察可以发现，每种连接情况下的各元素可以看成一个区间，每个区间只可能无交集或者完全是另一个的子集，不可能存在交集。比如n=4时，[1,2]和[3,4]无交集，n=6时，（12,36,45）情况下[4,5]是[3,6]的子集，[1,2]与其无交集。再观察可发现，每种情况下第一个元素必为[1,某偶数]，看到这里我就想到了之前做的LeetCode96题，假设某偶数为x，那么x将1~n分为[1,x]和[x,n]两个区间，因为[1,x]是必定存在的，所以可变的是中间x-1-1个值，后一半[x,n]全可变，即为n-x+1个值，所以G(n) = 求和G(x-2)*G(n-x+1)，x为所有可能的偶数。

本题n为偶数，所以代码修改一下与原题保持对应：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long[] array = new long[n / 2 + 1];
        array[0] = 1;
        array[1] = 1;
        int m = n/2;
        for(int i = 2; i <= m; i++){
            for(int j = 0; j < i; j++){
                array[i] = (array[i] + array[j] * array[i - j - 1] % 1000000007) % 1000000007;
            }
        }
        System.out.println(array[m]);
    }
}

注意及时取余，否则可能会溢出导致不能所有测试用例通过。

PS其他题目思路：

第一题 LeetCode 547朋友圈原题

第三题 不难，但是要注意中间元素为0的情况

第四题思路与第一题类似，用质数取数组再用并查集

(因为之前已过提前批，只能看同门的题，手痒做了一下😁，并没有完全在线测试，各位大佬轻拍)

第一次写这么多，感谢阅读。。