C++算法第十一天
本篇文章我们继续学习动态规划
第一题
题目链接
题目解析
代码原理
代码编写
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
//建表
vector<vector<int>> dp(m + 1, vector<int>(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(vector<vector<int>>& frame) {
int m = frame.size(), n = frame[0].size();
//建表
vector<vector<int>> dp(m + 1, vector<int>(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(vector<vector<int>>& matrix) {
int n = matrix.size();
//建表
vector<vector<int>> dp(n + 1,vector<int>(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(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
//建表
vector<vector<int>> dp(m + 1, vector<int>(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(vector<vector<int>>& dungeon) {
int m = dungeon.size(),n = dungeon[0].size();
//建表
vector<vector<int>> dp(m + 1, vector<int>(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.如何正确初始化：结合状态表示和状态转移方程，进行分析哪些地方存在越界的可能性
那么本篇文章的内容就先到此结束，我们下期文章再见！！！
记得一键三联哦
