创意设计网站公司,手机wap网站建设多少钱,室内设计效果图展板,企业微信下载app本篇文章我们继续学习动态规划 目录
第一题
题目链接
题目解析
代码原理
代码编写
第二题
题目链接
题目解析
代码原理
代码编写
第三题
题目链接
题目解析
代码原理
代码编写
第四题
题目链接
题目解析
代码原理
代码编写
第五题
题目链接
题目解析
代…本篇文章我们继续学习动态规划 目录
第一题
题目链接
题目解析
代码原理
代码编写
第二题
题目链接
题目解析
代码原理
代码编写
第三题
题目链接
题目解析
代码原理
代码编写
第四题
题目链接
题目解析
代码原理
代码编写
第五题
题目链接
题目解析
代码原理
代码编写
题后总结 第一题
题目链接
题目解析 代码原理 代码编写
class Solution {
public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(), n obstacleGrid[0].size(); //建表 vectorvectorint dp(m 1, vectorint(n 1)); //初始化 dp[0][1] 1;//当然这里dp[1][0] 1也是可以的 //填表 for(int i 1; i m; i) { for(int j 1; j n; j) { //状态转移方程 if(obstacleGrid[i - 1][j - 1] 0) dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } return dp[m][n]; }
};
第二题
题目链接
LCR 166. 珠宝的最高价值 - 力扣LeetCode
题目解析 代码原理 代码编写
class Solution {
public: int jewelleryValue(vectorvectorint frame) { int m frame.size(), n frame[0].size(); //建表 vectorvectorint dp(m 1, vectorint(n 1)); //初始化 dp[0][1] 0; //填表 for(int i 1; i m; i) { for(int j 1; j n; j) { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) frame[i - 1][j - 1]; } } return dp[m][n]; }
};
第三题
题目链接
931. 下降路径最小和 - 力扣LeetCode
题目解析 代码原理 代码编写
class Solution {
public: int minFallingPathSum(vectorvectorint matrix) { int n matrix.size(); //建表 vectorvectorint dp(n 1,vectorint(n 2, INT_MAX)); //初始化第一行 for(int j 0; j n 2; j) { dp[0][j] 0; } //填表 for(int i 1; i n 1; i) { for(int j 1; j n; j) { dp[i][j] min(min(dp[i - 1][j - 1], dp[i - 1][j]),dp[i - 1][j 1]) matrix[i - 1][j - 1]; } } int ret INT_MAX; for(int j 1; j n; j) { ret min(ret, dp[n][j]); } return ret; }
};
第四题
题目链接
64. 最小路径和 - 力扣LeetCode
题目解析 代码原理 代码编写
class Solution {
public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); //建表 vectorvectorint dp(m 1, vectorint(n 1, INT_MAX)); //初始化 dp[0][1] 0; //填表 for(int i 1; i m; i) { for(int j 1; j n; j) { dp[i][j] min(dp[i - 1][j],dp[i][j - 1]) grid[i - 1][j - 1]; } } return dp[m][n]; }
};
第五题
题目链接
174. 地下城游戏 - 力扣LeetCode
题目解析 代码原理 这里的状态方程有个小错误需要注意一下正确的我放在下面啦别看漏哦
正确的状态转移方程dp[i][j] min(dp[i][j 1],dp[i 1][j]) - cur[i][j]
代码编写
class Solution {
public: int calculateMinimumHP(vectorvectorint dungeon) { int m dungeon.size(),n dungeon[0].size(); //建表 vectorvectorint dp(m 1, vectorint(n 1, INT_MAX)); //初始化 dp[m][n - 1] dp[m - 1][n] 1; //填表 for(int i m - 1; i 0; i--) { for(int j n - 1; j 0; j--) { dp[i][j] min(dp[i][j 1], dp[i 1][j]) - dungeon[i][j]; dp[i][j] max(1,dp[i][j]); } } return dp[0][0]; }
};
题后总结
通过今天的题我们可以总结出以下几点
1.填表时需要使用原表上的数据时行列各减1
2.初始化部分的目的保证填表时不越界 保证填表时后面的数据正确
3.如何正确初始化结合状态表示和状态转移方程进行分析哪些地方存在越界的可能性
那么本篇文章的内容就先到此结束我们下期文章再见 记得一键三联哦
