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

经典动态规划，递推公式为dp[i][j] = grid[i][j] + max(dp[i-1][j],dp[i][j-1]),即自身加左一或者上一两种情况 下面注释掉的是学来的降低空间复杂度写法，逐行替换最终只用一个一维的dp数组

class Solution:
    def maxValue(self,grid):
        m,n = len(grid),len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(0,m):
            for j in range(0,n):
                dp[i][j] = grid[i][j] + max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]
    
# class Solution:
#     def maxValue(self , grid ):
#         # write code here
#         x, y = len(grid), len(grid[0])
#         dp = [0]*(y+1)
#         for i in range(0,x):
#             for j in range(1,y+1):
#                 dp[j] = max(dp[j-1],dp[j])+grid[i][j-1]
#         return dp[-1]