1.本周小结动态规划
周一
在关于动态规划，你该了解这些！ (opens new window)中我们讲解了动态规划的基础知识。
首先讲一下动规和贪心的区别，其实大家不用太强调理论上的区别，做做题，就感受出来了。
然后我们讲了动规的五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
后序我们在讲解动规的题目时候，都离不开这五步！
本周都是简单题目，大家可能会感觉 按照这五部来好麻烦，凭感觉随手一写，直接就过，越到后面越会感觉，凭感觉这个事还是不靠谱的。
最后我们讲了动态规划题目应该如何debug，相信一些录友做动规的题目，一旦报错也是凭感觉来改。
其实只要把dp数组打印出来，哪里有问题一目了然！
如果代码写出来了，一直AC不了，灵魂三问：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
周二
这道题目动态规划：斐波那契数 (opens new window)是当之无愧的动规入门题。
简单题，我们就是用来了解方法论的，用动规五部曲走一遍，题目其实已经把递推公式，和dp数组如何初始化都给我们了。
周三
动态规划：爬楼梯 (opens new window)这道题目其实就是斐波那契数列。
但正常思考过程应该是推导完递推公式之后，发现这是斐波那契，而不是上来就知道这是斐波那契。
在这道题目的第三步，确认dp数组如何初始化，其实就可以看出来，对dp[i]定义理解的深度。
dp[0]其实就是一个无意义的存在，不用去初始化dp[0]。
有的题解是把dp[0]初始化为1，然后遍历的时候i从2开始遍历，这样是可以解题的，然后强行解释一波dp[0]应该等于1的含义。
一个严谨的思考过程，应该是初始化dp[1] = 1，dp[2] = 2，然后i从3开始遍历。
这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。
一个绝佳的大厂面试题，第一道题就是单纯的爬楼梯，然后看候选人的代码实现，如果把dp[0]的定义成1了，就可以发难了，为什么dp[0]一定要初始化为1，此时可能候选人就要强行给dp[0]应该是1找各种理由。那这就是一个考察点了，对dp[i]的定义理解的不深入。
然后可以继续发难，如果一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。这道题目leetcode上并没有原题，绝对是考察候选人算法能力的绝佳好题。
这一连套问下来，候选人算法能力如何，面试官心里就有数了。
其实大厂面试最喜欢问题的就是这种简单题，然后慢慢变化，在小细节上考察候选人。
这道绝佳的面试题我没有用过，如果录友们有面试别人的需求，就把这个套路拿去吧。
我在通过一道面试题目，讲一讲递归算法的时间复杂度！ (opens new window)中，以我自己面试别人的真实经历，通过求x的n次方 这么简单的题目，就可以考察候选人对算法性能以及递归的理解深度，录友们可以看看，绝对有收获！
周四
这道题目动态规划：使用最小花费爬楼梯 (opens new window)就是在爬台阶的基础上加了一个花费，
这道题描述也确实有点魔幻。
题目描述为：每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
示例1：
输入：cost = [10, 15, 20] 输出：15
从题目描述可以看出：要不是第一步不需要花费体力，要不就是第最后一步不需要花费体力，我个人理解：题意说的其实是第一步是要支付费用的！。因为是当你爬上一个台阶就要花费对应的体力值！
所以我定义的dp[i]意思是也是第一步是要花费体力的，最后一步不用花费体力了，因为已经支付了。
之后一些录友在留言区说 可以定义dp[i]为:第一步是不花费体力，最后一步是花费体力的。
2.不同路径
力扣题目链接(opens new window)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
- 输入：m = 3, n = 7
- 输出：28
示例 2：
- 输入：m = 2, n = 3
- 输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 3：
- 输入：m = 7, n = 3
- 输出：28
示例 4：
- 输入：m = 3, n = 3
- 输出：6
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 10^9
思路
深搜
这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。
注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！
如图举例：
此时问题就可以转化为求二叉树叶子节点的个数
深搜的算法，其实就是要遍历整个二叉树。
这棵树的深度其实就是m+n-1（深度按从1开始计算）。
那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）
所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，是非常大的。
动态规划
机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。
按照动规五部曲来分析：
- 确定dp数组（dp table）以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
- 确定递推公式
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
- dp数组的初始化
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
- 确定遍历顺序
这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
- 举例推导dp数组
如图所示：
数论方法
在这个图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n - 2 步。
在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。
那么有几种走法呢？ 可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。
那么这就是一个组合问题了。
那么答案，如图所示：
求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。
总结
本文分别给出了深搜，动规，数论三种方法。
深搜当然是超时了，顺便分析了一下使用深搜的时间复杂度，就可以看出为什么超时了。
然后在给出动规的方法，依然是使用动规五部曲，这次我们就要考虑如何正确的初始化了，初始化和遍历顺序其实也很重要！
public class different_paths {public static int uniquePaths(int m, int n) {//接受两个整数参数m和n，分别代表网格的行数和列数，并返回到达右下角的不同路径数量。int[][] dp = new int[m][n];//一个二维数组dp，用于存储到达每个格子的不同路径数量。for (int i = 0; i < m; i++) {//初始化第一列的所有值为1，因为到达第一列的任何格子只有一种方式，即沿着第一列向下移动。dp[i][0] = 1;}for (int i = 0; i < n; i++) {//初始化第一行的所有值为1，因为到达第一行的任何格子只有一种方式，即沿着第一行向右移动。dp[0][i] = 1;}for (int i = 1; i < m; i++) {//计算到达每个格子的不同路径数量。对于每个格子(i, j)，到达该格子的路径数量等于到达其上方格子(i-1, j)的路径数量加上到达其左侧格子(i, j-1)的路径数量。for (int j = 1; j < n; j++) {dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];//返回到达右下角格子的不同路径数量。}
}
- 时间复杂度为
O(m * n^2) - 空间复杂度为
O(m * n)
状态压缩
public class different_paths {public int uniquePaths2(int m, int n) {//接受两个整数参数m和n，并返回到达右下角的不同路径数量。int[] dp = new int[n];//一维数组dp，用于存储到达每一行的最后一个格子的不同路径数量。Arrays.fill(dp, 1);//将dp数组的所有元素初始化为1，因为到达第一行的任何格子只有一种方式。for (int i = 1; i < m; i ++) {//计算到达每一行的最后一个格子的不同路径数量。对于每一行i（从第二行开始），到达该行的每个格子j的路径数量等于到达上一行的同一列的格子j-1的路径数量加上到达当前行的前一列的格子j的路径数量。for (int j = 1; j < n; j ++) {dp[j] += dp[j - 1];}}return dp[n - 1];}
}
时间复杂度为O(m * n)
空间复杂度为O(n)
3.不同路径 II
力扣题目链接(opens new window)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
- 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
- 输出：2 解释：
- 3x3 网格的正中间有一个障碍物。
- 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：
- 输入：obstacleGrid = [[0,1],[0,0]]
- 输出：1
提示：
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
思路
这道题相对于62.不同路径 (opens new window)就是有了障碍。
第一次接触这种题目的同学可能会有点懵，这有障碍了，应该怎么算呢？
62.不同路径 (opens new window)中我们已经详细分析了没有障碍的情况，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。
动规五部曲：
- 确定dp数组（dp table）以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
- 确定递推公式
递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。
- dp数组如何初始化
在62.不同路径 (opens new window)不同路径中
因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。
但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
如图：
下标(0, j)的初始化情况同理。
for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理
- 确定遍历顺序
从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，一定是从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
- 举例推导dp数组
拿示例1来举例如题：
对应的dp table 如图：
总结
本题是62.不同路径 (opens new window)的障碍版，整体思路大体一致。
但就算是做过62.不同路径，在做本题也会有感觉遇到障碍无从下手。
其实只要考虑到，遇到障碍dp[i][j]保持0就可以了。
也有一些小细节，例如：初始化的部分，很容易忽略了障碍之后应该都是0的情况。
public class different_pathsII {public int uniquePathsWithObstacles1(int[][] obstacleGrid) {//接受一个二维整数数组obstacleGrid作为参数，表示网格，其中1表示障碍物，0表示空地。该方法返回从左上角到右下角的不同路径数量。int m = obstacleGrid.length;//获取网格的行数m和列数n。int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//用于存储到达每个格子的不同路径数量。if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {//如果目标格子（右下角）或起点（左上角）有障碍物，则返回0，因为无法到达目的地。return 0;}for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {//初始化第一列的值。如果某行的第一列没有障碍物，则到达该列的路径数量为1。dp[i][0] = 1;}for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {//初始化第一行的值。如果某列的第一行没有障碍物，则到达该行的路径数量为1。dp[0][j] = 1;}for (int i = 1; i < m; i++) {//计算从第二行第二列开始的所有格子的路径数量。for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;//如果该格子没有障碍物，则到达该格子的路径数量等于到达其上方格子(i-1, j)的路径数量加上到达其左侧格子(i, j-1)的路径数量。如果该格子有障碍物，则到达该格子的路径数量为0。}}return dp[m - 1][n - 1];}}
时间复杂度为O(m * n)
空间复杂度为O(m * n)
空间优化版本
public class different_pathsII {public int uniquePathsWithObstacles2(int[][] obstacleGrid) {//接受一个二维整数数组obstacleGrid作为参数，表示网格，其中1表示障碍物，0表示空地。该方法返回从左上角到右下角的不同路径数量。int m = obstacleGrid.length;//获取网格的行数m和列数n。int n = obstacleGrid[0].length;int[] dp = new int[n];//一维数组dp，用于存储到达每一列的最后一个格子的不同路径数量。for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {//初始化第一行的值。如果第一行的某个格子没有障碍物，则到达该格子的路径数量为1。dp[j] = 1;}for (int i = 1; i < m; i++) {//外层循环遍历网格的每一行，从第二行开始。for (int j = 0; j < n; j++) {//内层循环遍历当前行的每个格子。if (obstacleGrid[i][j] == 1) {//如果当前格子有障碍物，则到达该格子的路径数量为0。dp[j] = 0;} else if (j != 0) {//如果当前格子没有障碍物，并且不是当前列的第一个格子（即j != 0），则到达该格子的路径数量等于到达当前列前一个格子的路径数量（即dp[j - 1]）。dp[j] += dp[j - 1];}}}return dp[n - 1];}
}
时间复杂度为O(m * n)
空间复杂度为O(n)
4.整数拆分
力扣题目链接(opens new window)
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
- 输入: 2
- 输出: 1
- 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
- 输入: 10
- 输出: 36
- 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
- 说明: 你可以假设 n 不小于 2 且不大于 58。
思路
动态规划
动规五部曲，分析如下：
- 确定dp数组（dp table）以及下标的含义
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
dp[i]的定义将贯彻整个解题过程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！
- 确定递推公式
可以想 dp[i]最大乘积是怎么得到的呢？
其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。
一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
那有同学问了，j怎么就不拆分呢？
j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。那么从1遍历j，比较(i - j) * j和dp[i - j] * j 取最大的。递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
也可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。
所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
那么在取最大值的时候，为什么还要比较dp[i]呢？
因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。
- dp的初始化
不少同学应该疑惑，dp[0] dp[1]应该初始化多少呢？
有的题解里会给出dp[0] = 1，dp[1] = 1的初始化，但解释比较牵强，主要还是因为这么初始化可以把题目过了。
严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。
拆分0和拆分1的最大乘积是多少？
这是无解的。
这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！
- 确定遍历顺序
确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。
注意 枚举j的时候，是从1开始的。从0开始的话，那么让拆分一个数拆个0，求最大乘积就没有意义了。
j的结束条件是 j < i - 1 ，其实 j < i 也是可以的，不过可以节省一步，例如让j = i - 1，的话，其实在 j = 1的时候，这一步就已经拆出来了，重复计算，所以 j < i - 1
至于 i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。
例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。
只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。
那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。
至于 “拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的” 这个我就不去做数学证明了，感兴趣的同学，可以自己证明。
- 举例推导dp数组
举例当n为10 的时候，dp数组里的数值，如下：
贪心
本题也可以用贪心，每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！
动态规划
public class Integer_Partition {public int integerBreak1(int n) {//接受一个整数n作为参数，并返回将其拆分后能得到的最大乘积。int[] dp = new int[n+1];//一个长度为n+1的整型数组dp，用于存储从1到n每个整数拆分后能得到的最大乘积。dp[2] = 1;//初始化dp[2]为1，因为2是最小的可以拆分的数，且2只能拆分为1+1，乘积为1。for(int i = 3; i <= n; i++) {//外层循环从3开始，因为2已经在上一步初始化了。for(int j = 1; j <= i-j; j++) {//内层循环遍历所有可能的拆分数j，使得j和i-j的和为i。dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));//对于每个i，尝试所有可能的拆分方式，计算j*(i-j)和j*dp[i-j]，取两者中较大的值，更新dp[i]。j*(i-j)表示将i拆分为j和i-j的乘积，j*dp[i-j]表示将i拆分为j和剩余部分（i-j）的最大乘积。}}return dp[n];}}
时间复杂度：O(n^2)
空间复杂度：O(n)
贪心
public class Integer_Partition {public int integerBreak2(int n) {if(n == 2) return 1;//如果n为2，直接返回1，因为2不能拆分为更小的正整数。if(n == 3) return 2;//如果n为3，直接返回2，因为3的最佳拆分是1+1+1，乘积为1，但3本身作为单个整数的乘积为3。int result = 1;while(n > 4) {//每次循环减少n的值3，并更新result为原来的3倍。这是因为对于大于4的数，每次拆分出一个3，都能保证乘积最大。n-=3;result *=3;}return result*n;//循环结束后，n的值将小于或等于4。此时，根据n的值（可能是2、3或4），直接与result相乘得到最终的最大乘积。}
}
时间复杂度：O(n)
空间复杂度：O(1)
5.不同的二叉搜索树
力扣题目链接(opens new window)
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
思路
这道题目描述很简短，但估计大部分同学看完都是懵懵的状态，这得怎么统计呢？
关于什么是二叉搜索树，我们之前在讲解二叉树专题的时候已经详细讲解过了，也可以看看这篇二叉树：二叉搜索树登场！ (opens new window)再回顾一波。
了解了二叉搜索树之后，我们应该先举几个例子，画画图，看看有没有什么规律，如图：
n为1的时候有一棵树，n为2有两棵树，这个是很直观的。
来看看n为3的时候，有哪几种情况。
当1为头结点的时候，其右子树有两个节点，看这两个节点的布局，是不是和 n 为2的时候两棵树的布局是一样的啊！
（可能有同学问了，这布局不一样啊，节点数值都不一样。别忘了我们就是求不同树的数量，并不用把搜索树都列出来，所以不用关心其具体数值的差异）
当3为头结点的时候，其左子树有两个节点，看这两个节点的布局，是不是和n为2的时候两棵树的布局也是一样的啊！
当2为头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！
发现到这里，其实我们就找到了重叠子问题了，其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。
思考到这里，这道题目就有眉目了。
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
如图所示：
此时我们已经找到递推关系了，那么可以用动规五部曲再系统分析一遍。
- 确定dp数组（dp table）以及下标的含义
dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。
以下分析如果想不清楚，就来回想一下dp[i]的定义
- 确定递推公式
在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。
所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
- dp数组如何初始化
初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。
那么dp[0]应该是多少呢？
从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。
从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
所以初始化dp[0] = 1
- 确定遍历顺序
首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
那么遍历i里面每一个数作为头结点的状态，用j来遍历。
- 举例推导dp数组
n为5时候的dp数组状态如图：
当然如果自己画图举例的话，基本举例到n为3就可以了，n为4的时候，画图已经比较麻烦了。
public class Different_Binary_Search_Trees {public int numTrees(int n) {//接受一个整数n作为参数，表示节点的数量，并返回可以形成的不同二叉搜索树的数量。int[] dp = new int[n + 1];//一个长度为n + 1的整型数组dp，用于存储从0到n个节点时不同二叉搜索树的数量。dp[0] = 1;//初始化dp[0]和dp[1]。对于0个节点，有一种空树的情况，对于1个节点，有一种单节点树的情况。dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {//内层循环遍历从1到i的所有可能的根节点。dp[i] += dp[j - 1] * dp[i - j];//对于每个i，计算以j为根节点时的不同二叉搜索树的数量，并将结果累加到dp[i]。这里dp[j - 1]表示左子树的不同二叉搜索树的数量（j - 1个节点），dp[i - j]表示右子树的不同二叉搜索树的数量（i - j个节点）。}}return dp[n];}
}
时间复杂度：O(n^2)
空间复杂度：O(n)
