做过很多次的，典型的2维dp，所以就不复述了。这个算法的时间复杂度是O（MN），如果在原先的矩阵上改的话空间复杂度是O（1）。
class Solution:
def maxValue1(self, grid: List[List[int]]) -> int:
rows, columns = len(grid), len(grid[0])
res = [[0]*columns for i in range(rows)]
res[0][0] = grid[0][0]
for y in range(1, columns):
res[0][y] = res[0][y-1] + grid[0][y]
for x in range(1, rows):
res[x][0] = res[x-1][0] + grid[x][0]
for x in range(1, rows):
for y in range(1, columns):
res[x][y] = max(res[x-1][y], res[x][y-1]) + grid[x][y]
return res[-1][-1]
def maxValue2(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for j in range(1, n):
grid[0][j] += grid[0][j - 1]
for i in range(1, m):
grid[i][0] += grid[i - 1][0]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
return grid[-1][-1]PREVIOUSjz046.把数字翻译成字符串