字节跳动笔试第二题求解答

leetcode96题同样思路

卡特兰数，可以百度一下

每次用一个点跟其他点连接，然后就出出现两个前面解决过的子问题，比如说： F(6) = F(4)*F(0) + F(2)*F(2) + F(4)*F(0) F(8) = F(6)*F(0) + F(4)*F(2) + F(2)*F(4) + F(0)*F(6) import sys def main():     n = int(sys.stdin.readline().strip())     a = [0 for i in range(1000+2)]     a[0] = 1     a[2] = 1     a[4] = 2     if n == 2 or n == 4:         return a[n]     for i in range(6, n+1):         if i % 2 != 0:             continue         res = 0         total = i - 2         temp = i - 2         while temp >= 0:             l = temp             r = total - l             res = (res + ((a[l]%1000000007)* (a[r]%1000000007))%1000000007)%1000000007             temp -= 2         a[i] = res     return a[n] print(main())

厉害了 昨天看了一个小时都没看出来 我太难了

大佬们，我实在想不出来哪里有问题，可是昨天提交就是70%，能帮我看一下吗

Dp过了80

兄弟，很吊，字也写的很漂亮

poj 2084

#圆的路径数，100%ac n=int(input()) res=[0]*(n+1) res[2]=1 for i in range(2,n+1,2):     res[i]+=(res[i-2]*2)     for j in range(2,(i-4)+1,2):         res[i]+=(res[j]*res[i-j-2]) print(res[n]%1000000007)