剑指 Offer 47. 礼物的最大价值

class Solution(object):
    def maxValue(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return
        m = len(grid)
        n = len(grid[0])
        max_val = [[0 for i in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                left = 0
                up = 0
                if i > 0:
                    up = max_val[i-1][j]
                if j > 0:
                    left = max_val[i][j-1]
                max_val[i][j] = max(up, left) + grid[i][j]
        return max_val[-1][-1]