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

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

    # 记录当前位置的礼物的最大

        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):

                # 初始化第一行，第一列的元素，它不可能从上面，或者左边移动过来，所以说它的大小就是它最大的价值

                if i == 0 and j == 0:
                    print(grid[0][0])
                    dp[i][j] = grid[i][j]

                # 棋盘中非第一行，非第一列中的元素的最大的情况，应该取他上面一行或者左边一列的最大值加上自身的礼物价值

                elif len(grid) > i > 0 and len(grid[0]) > j > 0:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

                # 棋盘的第一行只能从左移动过去，从上面移动下来不可能

                elif i-1 < 0:
                    print("行列", i, j)
                    dp[i][j] = dp[i][j-1]+grid[i][j]

                # 棋盘的第一列，不可能从左边移动过来，所以只能从上面移动过来
                elif j-1 < 0:
                    dp[i][j] = dp[i-1][j] + grid[i][j]

        return dp[M-1][N-1]