Leetcode剑指-Offer-47-礼物的最大价值-Python实现

• 题目要求：

• 思路：

  • 创建一个二维数组，用来保存每个格子能取到的礼物的最大价值
  • 遍历数组，取到当前的礼物的最大价值是这个礼物的 (上一格，或左面一格) 两个中最大的价值 + 当前礼物的价值，把这个值存在二维数组中。
  • 最后返回二维数组的最后一个值就是最大的价值。
• 核心代码：

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]