【OJ】动归练习三
1. LCR166. 珠宝的最高价值
1.1 分析
- 状态表示 以[i][j]位置为结尾，表示到达[i][j]位置时，此时的最大价值。
- 状态转移方程 要在[i][j]位置时候得到最大价值，要么从它上面的一个下来，要么从它左边一个过来，但是选择的是价值更大的那一个,再加上它本身那一个所对应的价值 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]
- 初始化 这里也是要涉及到可能会越界问题，就直接多开一行和一列，为了不影响价值计算的结果就全部都初始化为0。这里得注意下标的映射，此时在dp[i][j]位置就对应frame[i-1][j-1]，写代码时候得注意。
- 填表顺序 从上往下，从左往右
- 返回值 直接返回dp[m][n]就行
1.2 代码
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m=frame.size();
int n=frame[0].size();
vector<vector<int>> dp(m+1,vector<int> (n+1));
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];
}
};2. 931.下降路径最小和
2.1 分析
- 状态表示 同样是以[i][j]位置结尾，来找下降路径的最小和。
- 状态转移方程
想要到达[i][j]位置有三种方式[i-1][j-1]和[i-1][j]还有[i-1][j+1]，
在这里插入图片描述
而题目要求的是最小和，那么就取这三个位置的最小值和，再加上这个位置本身的值
- 初始化 像绿色星号标注的位置可能会存在越界的问题，所以就多开两列和一行。但是想让填表时候第一行位置所在的值不变，那么新开空间的第一行就初始化为0：
但如果也把左边开的这一列初始化为0，那么红色格子这格的最小值和可能就会用到这个0，所以这里不能写0，为了不改变选择的结果，就把这些初始化为INT_MAX
- 填表顺序 从上往下
- 返回值 返回最后一行最小的值
2.2 代码
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;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min(dp[i-1][j-1],min(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;
}
};3. 64.最小路径和
3.1 分析
- 状态表示 以[i][j]为结尾，找最小和。 dp[i][j]表示到达[i][j]位置时，最小路径和。
- 状态转移方程 根据最近的一步划分问题。 到到达[i][j]位置有两种方式，一种从上面，一种从左边
一种是以最小的路径到上面，然后加上当前位置的值； 另一种是最小的路径到左边，然后加上当前位置的值。
所以到达的dp[i][j]最小值就是，两种中取最下的那一个
- 初始化
这里可能会存在越界访问的情况，所以多开一行和一列。但要注意里面填的值，要保证在后面计算的结果是正确的。
第一行第一列为了值不被改变，就得在新开空间的上面一格和左边一格的值为0，其他的为了不影响后面取最小值和的计算，都初始化为
INT_MAX
- 填表顺序 从上往下，从左往右
- 返回值 要求每个位置的最小值，就直接返回dp[m][n]
3.2 代码
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]=dp[1][0]=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];
}
};有问题请指出，大家一起进步！！！
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录