| 1 | 1 | 2 | 5 | 14 | 42 | ... |
| n=0 | n=1 | n=2 | n=3 | n=4 | n=5 | ... |
对于卡特兰数:本质上是一个数列，在应用上往往表示对于某个n作为限定条件，其代表了对于的组合情况是多少？
public class Main { public static void main(String[] args) { System.out.println(nums_1(6));
} private static int nums_0(int n){ if (n == 0 || n == 1) return 1; int S0 = 1; int S1 = 1; int out= 0; for (int i = 0; i <= n-1; i++) { out+=nums_0(i)*nums_0(n-1-i); } return out; } private static int nums_1(int n){ if (n == 0 || n == 1) return 1; int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { for (int m = 0; m < i; m++) { dp[i] += dp[m]*dp[i-1-m]; } } return dp[n]; } }
在这里:动态规划相对于递归的区别是，求解S_n的过程中，先求S_0，而递归是想先求S_n-1，想求二求不得，只有逐层递归求解，直到S_0、S_1，再返回，这将导致占用大量的栈空间，并且因为没
有对中间求解结果S_k保存，会导致重复求解某个S_k。
原文：https://www.cnblogs.com/iuyy/p/13507678.html