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

题目：https://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param grid int整型二维数组 
# @return int整型
#
class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        #从最后一步倒推，最后一步要么来源于右下角的左边的一格，要么来源于右下角的上面的一格。
        #从头开始每一步贪心地走是不行的，要找全局最优解。
        #要用倒推思想，走的每一步都是来源于上步的最优。要一个row*col的记忆数组才行
        #一共要走row+col步
        #i行j列位置的最大价值m(i,j)=max(m(i-1,j),m(i,j-1))
        #特殊情况
        if grid==[[]]:
            return 0
         
        row=len(grid)#总行数
        col=len(grid[0])#总列数
        #左上角的坐标[0][0]

        #逐个填写二维记忆数组，记录每个位置能累计得到的最大价值
        maxv=[[grid[0][0] for i in range(col)] for i in range(row)]
        #注意这有个二维列表的生成的坑      
        #填maxv数组的边界
        for j in range(1,col):
            maxv[0][j]=sum(grid[0][:j])+grid[0][j]#maxv第一行的位置的最大价值
        
        colsum=grid[0][0]
        for i in range(1,row):
            colsum=colsum+grid[i][0]#maxv第一列的位置的最大价值
            maxv[i][0]=colsum
                
        for i in range(1,row):
            for j in range(1,col):
                maxv[i][j]=max(maxv[i-1][j],maxv[i][j-1])++grid[i][j]
                
        return maxv[row-1][col-1]

有一个二维列表的生成的坑，用maxv=[[0 for i in range(col)] for i in range(row)]这样的方式生成。如果用[[0]*4]*5生成，后面想赋值每个位置上的数据会有问题。在这种情况下，[0,0,0,0] 直接拷贝了5份，但地址指向的是同一个，所以改变其中一个，会改变每一行这一列的数。

简洁写法：

上面的做法太啰嗦了，不需要新增一个与grid一样大小的maxv来记录最大价值，直接在grid上算就好了。

class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        m=len(grid)
        n=len(grid[0])
        #以下两个for是边界条件初始化
        for i in range(1,m):
            grid[i][0]=grid[i-1][0]+grid[i][0]
        for j in range(1,n):
            grid[0][j]=grid[0][j-1]+grid[0][j]
        #遍历以后每个位置
        for i in range(1,m):
            for j in range(1,n):
                grid[i][j]=max(grid[i-1][j],grid[i][j-1])+grid[i][j]
        return grid[m-1][n-1]

需要注意的是，for循环的起始下标是1开始的，不然下标i-1是会有问题的。