共计 936 个字符,预计需要花费 3 分钟才能阅读完成。
- 题目要求:
-
思路:
- 创建一个二维数组,用来保存每个格子能取到的礼物的最大价值
- 遍历数组,取到当前的礼物的最大价值是这个礼物的 (上一格,或左面一格) 两个中最大的价值 + 当前礼物的价值,把这个值存在二维数组中。
- 最后返回二维数组的最后一个值就是最大的价值。
- 核心代码:
dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
# 处理了一下边界问题,如果当前礼物是第一个格子,那么它的最大价值就是它本身的最大价值
if i == 0 and j == 0:
dp[i][j] = grid[0][0]
# 如果当前的格子是在第一行,而且不是第一行的第一个,也就是说它没有上一行格子,那么它的价值是它本身加上它左面的格子
elif i == 0 and j != 0:
dp[i][j] = dp[i][j-1] + grid[i][j]
# 如果当前格子是在第一列,而且不是第一列的第一个,也就是说它没有左边的格子,那么它的价值是它本身加上它上面的格子
elif j == 0 and i != 0:
dp[i][j] = dp[i - 1][j] + grid[i][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
- 完整代码:
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == 0 and j == 0:
dp[i][j] = grid[0][0]
elif i == 0 and j != 0:
dp[i][j] = dp[i][j-1] + grid[i][j]
elif j == 0 and i != 0:
dp[i][j] = dp[i - 1][j] + grid[i][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
正文完