Leetcode Link: 剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode）
题目
解法一
思路：
当前位置只收到左边和上边的影响
dp[i][j] 表示走到grid[i][j]时的礼物最大价值。
题解：
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
dp[0][0] = grid[0][0]
for i in range(1,len(grid[0])):
dp[0][i] = dp[0][i-1] + grid[0][i]
for i in range(1,len(grid)):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,len(grid)):
for j in range(1, len(grid[0])):
dp[i][j] = max(dp[i-1][j], dp[i][j-1])+grid[i][j]
return dp[-1][-1]可以进一步许做状态压缩。
只收到本行和上一行的影响。