题解 | #礼物的最大价值#

二维 dp 问题,初始值 dp[0][0] = grid[0][0] 状态转移方程为：

dp[i][j] = dp[i][j - 1] + grid[i][j] i == 0 & j > 0 dp[i][j] = dp[i - 1][j] + grid[i][j] i > 0 & j == 0 dp[i][j] = max(dp[i -1][j], dp[i][j - 1]) + grid[i][j]

最终到达右下角值为 获取礼物的最大价值

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param grid int整型二维数组 
# @return int整型
#
class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        # write code here
        if not grid or not grid[0]: return 0
        dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if i == j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0 and j > 0:
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                elif i > 0 and j == 0:
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                elif i > 0 and j > 0:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[-1][-1]