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];
}
};
想要到达[i][j]位置有三种方式[i-1][j-1]和[i-1][j]还有[i-1][j+1],
而题目要求的是最小和,那么就取这三个位置的最小值和,再加上这个位置本身的值
但如果也把左边开的这一列初始化为0,那么红色格子这格的最小值和可能就会用到这个0,所以这里不能写0,为了不改变选择的结果,就把这些初始化为INT_MAX
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;
}
};
一种是以最小的路径到上面,然后加上当前位置的值; 另一种是最小的路径到左边,然后加上当前位置的值。
所以到达的dp[i][j]最小值就是,两种中取最下的那一个
INT_MAX
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];
}
};
有问题请指出,大家一起进步!!!