文章目录【62.不同路径】【63.不同路径II】【343.整数拆分】【96.不同的二叉搜索树】【62.不同路径】思路动态规划机器人从(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]也同理。所以初始化代码为for (int i 0; i m; i) dp[i][0] 1; for (int j 0; j n; j) dp[0][j] 1;确定遍历顺序这里要看一下递推公式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数组如图所示classSolution{public:intuniquePaths(intm,intn){// dp[i][j]表示从(0,0)到(i,j)有多少种方法vectorvectorintdp(m,vectorint(n,0));for(inti0;im;i){dp[i][0]1;}for(intj0;jn;j){dp[0][j]1;}for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}};【63.不同路径II】思路和上一题一样有障碍的地方不进行初始化和计算即可。classSolution{public:intuniquePathsWithObstacles(vectorvectorintobstacleGrid){intmobstacleGrid.size();intnobstacleGrid[0].size();if(obstacleGrid[m-1][n-1]1||obstacleGrid[0][0]1)//如果在起点或终点出现了障碍直接返回0return0;vectorvectorintdp(m,vectorint(n,0));for(inti0;imobstacleGrid[i][0]0;i)dp[i][0]1;for(intj0;jnobstacleGrid[0][j]0;j)dp[0][j]1;for(inti1;im;i){for(intj1;jn;j){if(obstacleGrid[i][j]0){dp[i][j]dp[i-1][j]dp[i][j-1];}elsecontinue;}}returndp[m-1][n-1];}};【343.整数拆分】思路dp[i]分拆数字i可以得到的最大乘积为dp[i]。dp[i]最大乘积是怎么得到的呢其实可以从1遍历j然后有两种渠道得到dp[i].一个是j * (i - j) 直接相乘。一个是j * dp[i - j]相当于是拆分(i - j)对这个拆分不理解的话可以回想dp数组的定义。注意 枚举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]正好可以通过我们初始化的数值求出来classSolution{public:intintegerBreak(intn){vectorintdp(n1);dp[2]1;for(inti3;in;i){for(intj1;ji/2;j){dp[i]max(dp[i],max(j*(i-j),j*dp[i-j]));}}returndp[n];}};【96.不同的二叉搜索树】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来遍历。代码如下for(inti1;in;i){for(intj1;ji;j){dp[i]dp[j-1]*dp[i-j];}}举例推导dp数组n为5时候的dp数组状态如图classSolution{public:intnumTrees(intn){vectorintdp(n1);dp[0]1;for(inti1;in;i){for(intj1;ji;j){dp[i]dp[j-1]*dp[i-j];}}returndp[n];}};