AcWing 60. 礼物的最大价值(三种写法)
原题链接
中等
作者:
二十七杯酒
,
2020-12-30 15:27:12
,
所有人可见
,
阅读 340
礼物的最大价值(dp、备忘)
C++ 代码
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
if(!grid.size() || !grid[0].size())
return 0;
int rows = grid.size(), cols = grid[0].size();
//判断边界不新开数组
for(int i = 0; i < rows; i ++ )
for(int j = 0; j < cols; j ++ ){
if(i == 0 && j == 0)continue;
else if(i == 0)
grid[i][j] += grid[i][j - 1];
else if(j == 0)
grid[i][j] += grid[i - 1][j];
else
grid[i][j] += max(grid[i - 1][j],
grid[i][j - 1]);
}
return grid[rows - 1][cols - 1];
/*不判断边界并新开数组
vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, 0));
for(int i = 1; i <= rows; i ++ )
for(int j = 1; j <= cols; j ++ ){
dp[i][j] = grid[i - 1][j - 1] + max(dp[i - 1][j],
dp[i][j - 1]);
}
return dp[rows][cols];*/
/*判断边界并新开数组
vector<vector<int>> dp(rows,vector<int>(cols, 0));
for(int i = 0; i < rows; i ++ )
for(int j = 0; j < cols; j ++ ){
if(i == 0 && j == 0)
dp[i][j] = grid[i][j];
else if(i == 0)
dp[i][j] = grid[i][j] + dp[i][j - 1];
else if(j == 0)
dp[i][j] = grid[i][j] + dp[i - 1][j];
else
dp[i][j] = grid[i][j] + max(dp[i - 1][j],
dp[i][j - 1]);
}
return dp[rows - 1][cols - 1];*/
}
};