菏泽去哪了做网站,韩国比分预测,留学公司网站怎么做,php做网站导购模板感觉dp的题真的很适合背#xff0c;当然不是死记硬背#xff0c;而是当做一种模板题#xff0c;出来一道新的题就往模板题上面去靠#xff0c;如果套对模板的话剩下的事情其实就简单了。所以只要看一遍解法知道大致思路其实就够了#xff0c;毕竟大部分dp的代码也不算难写…感觉dp的题真的很适合背当然不是死记硬背而是当做一种模板题出来一道新的题就往模板题上面去靠如果套对模板的话剩下的事情其实就简单了。所以只要看一遍解法知道大致思路其实就够了毕竟大部分dp的代码也不算难写。 62.不同路径
先是使用二维dp数组的方法结果发现二维数组的定义有点忘了于是乱写了一个没想到对了就是vectorvectorint dp(m, vectorint(n));
其他部分的话就没有太多好说的。
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n));for(int i0; im; i){dp[i][0] 1;}for(int j0; jn; j){dp[0][j] 1;}for(int i1; im; i){for(int j1; jn; 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) {vectorint dp(n);for(int i0; in; i){dp[i] 1;}for(int j1; jm; j){for(int i1; in; i){dp[i] dp[i] dp[i-1];}cout endl;}return dp[n-1];}
};
class Solution {
public:int uniquePaths(int m, int n) {vectorint dp(m);for(int i0; im; i){dp[i] 1;}for(int j1; jn; j){for(int i1; im; 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(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1){return 0;}vectorint dp(n);dp[0] 1;for(int i0; in; i){if(obstacleGrid[0][i] 1){break;}dp[i] 1;}for(int j1; jm; j){for(int i1; in; 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。这个时候我们就不能像上一题一样从i1开始了而是要从i0开始但是此时又出现了问题i0的是时候dp[i-1]又变成非法访问了所以要再加一个i0的判断最终的代码如下
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1){return 0;}vectorint dp(n);dp[0] 1;for(int i0; in; i){if(obstacleGrid[0][i] 1){break;}dp[i] 1;}for(int j1; jm; j){for(int i0; in; i){if(obstacleGrid[j][i] 1){dp[i] 0;}else if(i0){dp[i] dp[i] dp[i-1];}}}return dp[n-1];}
}; 验证一下上题的结论用m也能通过
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if(obstacleGrid[0][0]1 || obstacleGrid[m-1][n-1]1){return 0;}vectorint dp(m);dp[0] 1;for(int j0; jm; j){if(obstacleGrid[j][0] 1){break;}dp[j] 1;}for(int i1; in; i){for(int j0; jm; j){if(obstacleGrid[j][i] 1){dp[j] 0;}else if(j0){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) {vectorint dp(n1);dp[1] 0;dp[2] 1;for(int i3; in; i){for(int j1; ji; j){dp[i] max(dp[i], max(j*dp[i-j], j*(i-j)));}}return dp[n];}
};
本题我就是漏了里面的max以为只要写j*dp[i-j]即可就错了。
还有就是我这么定义n1的dp数组一定要注意终止条件要设置成i n否则就会出现dp[n]是0的情况害我想半天。 96.不同的二叉搜索树
本题其实是相当有难度的一周目记得做到的时候毫无思路但也因此这个题给我留下了深刻的印象清楚地知道就是从i处对数组截断两边取dp数组得到的值最后算个乘积所以一遍就做出来了。
class Solution {
public:int numTrees(int n) {vectorint dp(n1);dp[0] 1;dp[1] 1;for(int i2; in; i){for(int j1; ji; j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
};
