【剑指offer】礼物的最大价值 python

【题目描述】

在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？

【思路解析】

动态规划解决，当前格所能获得的最大价值等于max(左边，上边)+该格的价值。采用一个二维数组保存中间结果，最终返回右下角格的价值即可，时间复杂度等于格数。

在此基础上，书中的一种优化方式是，由于当前格的更新只与其上与左的格有关，因此可以只保存当前格左与上的值，用一个长度为cols的一维数组即可，保存下图中的13，11，14，22这四个价值。节约了空间。

在循环体中的更新方式：

up=temp[j]
left=temp[j-1]

temp[j]=max(up,left)+values[i*rows+j]

【代码】

#!coding:utf-8
class Solution:
    def getmaxValue(self, values, rows, cols):
        if not values or rows<=0 or cols <=0:
            return 0
        temp = [[0] * cols]*rows
        print(temp[1][2])

        for i in range(rows):
            for j in range(cols):
                left = 0
                up = 0
                if i > 0:
                    up=temp[i-1][j]
                if j > 0:
                    left=temp[i][j-1]
                temp[i][j] = max(up,left) + values[i*rows+j]
        return temp[rows-1][cols-1]
s = Solution()
a = s.getmaxValue([1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5],4,4)

优化：
class Solution:
    def getmaxValue(self, values, rows, cols):
        if not values or rows<=0 or cols <=0:
            return 0
        temp = [0] * cols

        for i in range(rows):
            for j in range(cols):
                left = 0
                up = 0

                if i > 0:
                    up = temp[j]
                if j > 0:
                    left = temp[j-1]
                temp[j] = max(up,left) + values[i*rows+j]
        return temp[-1]