这题也没有要求不能修改原始数组对不,所以直接把原始数组第一行当做辅助空间
源代码:
class Solution {
public int getMaxValue(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
// 当前元素上面、左边的值
int fromUp, fromLeft;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
fromUp = 0;
fromLeft = 0;
if (i != 0) {
// 当前元素上边的值就是grid第一行当前位置的值
fromUp = grid[0][j];
}
if (j != 0) {
// 当前元素左边的值就是grid第一行当前位置左边的值
fromLeft = grid[0][j - 1];
}
grid[0][j] = Math.max(fromLeft, fromUp) + grid[i][j];
}
}
return grid[0][cols - 1];
}
}