dfs思路(好写超时)
class Solution {
public:
int maxv = 0;
void dfs(vector<vector<int>>& grid, int x, int y, int v){
if(x == grid.size() - 1 && y == grid[0].size() - 1){
maxv = max(maxv, v + grid[x][y]);
return ;
}
if(x >= grid.size() || y >= grid[0].size()) return ;
dfs(grid, x + 1, y, v + grid[x][y]);
dfs(grid, x, y + 1, v + grid[x][y]);
}
int getMaxValue(vector<vector<int>>& grid) {
dfs(grid, 0, 0, 0);
return maxv;
}
};
dp
class Solution {
public:
int getMaxValue(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int f[n + 1][m + 1];
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m; j ++ ){
f[i][j] += grid[i - 1][j - 1];
if(i > 1) f[i][j] = max(f[i][j], f[i - 1][j] + grid[i - 1][j - 1]);
if(j > 1) f[i][j] = max(f[i][j], f[i][j - 1] + grid[i - 1][j - 1]);
}
}
return f[n][m];
}
};