【代码随想录day33】【C++复健】62.不同路径；63. 不同路径 II；343. 整数拆分；96.不同的二叉搜索树

感觉dp的题真的很适合背，当然不是死记硬背，而是当做一种模板题，出来一道新的题就往模板题上面去靠，如果套对模板的话剩下的事情其实就简单了。所以只要看一遍解法知道大致思路其实就够了，毕竟大部分dp的代码也不算难写。

62.不同路径

先是使用二维dp数组的方法，结果发现二维数组的定义有点忘了，于是乱写了一个，没想到对了，就是vector<vector<int>> dp(m, vector<int>(n));

其他部分的话就没有太多好说的。

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n));for(int i=0; i<m; i++){dp[i][0] = 1;}for(int j=0; j<n; j++){dp[0][j] = 1;}for(int i=1; i<m; i++){for(int j=1; j<n; j++){dp[i][j] = dp[i][j-1] + dp[i-1][j];}}return dp[m-1][n-1];}
};

然后重点说下这个一维的解法：
第一遍写的时候把i和j的顺序写反了，结果就是完全不对了。一开始觉得不就是遍历顺序从横着变成竖着嘛，有什么不一样的？

思考良久，发现是在定义这个dp数组的时候，我们把长度定义成了dp[n]，而实际上每次循环经过的是m次，简单来说就是会把值存错位置，导致无法得到正确结果。

可以对比一下下面这两段代码：

class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);for(int i=0; i<n; i++){dp[i] = 1;}for(int j=1; j<m; j++){for(int i=1; i<n; i++){dp[i] = dp[i] + dp[i-1];}cout << endl;}return dp[n-1];}
};

class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(m);for(int i=0; i<m; i++){dp[i] = 1;}for(int j=1; j<n; j++){for(int i=1; i<m; i++){dp[i] = dp[i] + dp[i-1];}cout << endl;}return dp[m-1];}
};

这两段代码都是可以正确提交的，区别在于，当我们想要变更循环顺序的时候，需要把dp数组的定义和初始化也都相应的变一下，不然就会发生报错。

总结一下，就是dp数组长度要与内层循环相等，写出来之后我自己都吓了一跳，这么简单的道理我怎么就没想到呢。当我们要动态更新一个长度为n的数组的时候，当然是每次循环都把这n个数都更新一遍，然后重复m次才对嘛。

63. 不同路径 II

有了上一题的结论做基础，本题即使是一维数组，也必将一遍拿下... 吗？

写了一套看似没什么问题的代码，实际上却没法全过：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1){return 0;}vector<int> dp(n);dp[0] = 1;for(int i=0; i<n; i++){if(obstacleGrid[0][i] == 1){break;}dp[i] = 1;}for(int j=1; j<m; j++){for(int i=1; i<n; i++){if(obstacleGrid[j][i] == 1){dp[i] = 0;}else{dp[i] = dp[i] + dp[i-1];}}}return dp[n-1];}
};

问题出在哪里了？我们在循环的时候，如果按上一题一样，实际上是默认每次循环的dp[0]都是等于1的，但是本题当中却不能做这样的假设，因为如果在某次循环的0号位有一个障碍物，从此时开始的dp[0]应该是0才对，而并不是1。这个时候我们就不能像上一题一样从i=1开始了，而是要从i=0开始，但是此时又出现了问题，i=0的是时候，dp[i-1]又变成非法访问了，所以要再加一个i>0的判断，最终的代码如下：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1){return 0;}vector<int> dp(n);dp[0] = 1;for(int i=0; i<n; i++){if(obstacleGrid[0][i] == 1){break;}dp[i] = 1;}for(int j=1; j<m; j++){for(int i=0; i<n; i++){if(obstacleGrid[j][i] == 1){dp[i] = 0;}else if(i>0){dp[i] = dp[i] + dp[i-1];}}}return dp[n-1];}
};

 验证一下上题的结论，用m也能通过：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1){return 0;}vector<int> dp(m);dp[0] = 1;for(int j=0; j<m; j++){if(obstacleGrid[j][0] == 1){break;}dp[j] = 1;}for(int i=1; i<n; i++){for(int j=0; j<m; j++){if(obstacleGrid[j][i] == 1){dp[j] = 0;}else if(j>0){dp[j] = dp[j] + dp[j-1];}}}return dp[m-1];}
};

最后就是，其实买你对这种比较难的题，其实没必要非得用一维dp数组的思路去想，思路上面会相对复杂。

343. 整数拆分

一周目其实已经做过这题，二周目试图复现思路，但漏了情况。

1 外层的max的含义：

dp[i]代表之前算出的乘积中最大的那个，后面的那个代表本次的新结果的乘积，两个比较之后取一个最大值，代表动态更新的最大乘积。

2 内层的max的含义：

j*dp[i-j]代表分j出来，并且拿剩下的继续拆分。因为dp[i-j]代表的是将i-j至少拆成2个值之后的最大乘积，保留i-j原本的值不进行拆分的情况并不在此列。因此我们此处还需要一个额外的max。

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[1] = 0;dp[2] = 1;for(int i=3; i<=n; i++){for(int j=1; j<i; j++){dp[i] = max(dp[i], max(j*dp[i-j], j*(i-j)));}}return dp[n];}
};

本题我就是漏了里面的max，以为只要写j*dp[i-j]即可，就错了。

还有就是我这么定义n+1的dp数组，一定要注意终止条件要设置成i <= n，否则就会出现dp[n]是0的情况（害我想半天）。

96.不同的二叉搜索树

本题其实是相当有难度的，一周目记得做到的时候毫无思路，但也因此这个题给我留下了深刻的印象，清楚地知道就是从i处对数组截断，两边取dp数组得到的值最后算个乘积，所以一遍就做出来了。

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