面试题47：礼物的最大价值

题目：

思路:
这道题是动态规划的思想，到i，j位置的礼物最大价值 只和左上有关，用一个二维数组来缓存值，得到最大的礼物值，具体如下：

47 礼物的价值.png

代码：

class Solution(object):
    def maxValue(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # write code here
        rows = len(grid)
        cols = len(grid[0])
        if grid == [] or rows<=0 or cols<=0:
            return None
        maxValue = [[0 for i in range(cols)] for j in range(rows)]
        for i in range(rows):
            for j in range(cols):
                up = 0
                left = 0
                if i > 0:  #行大于0
                    up = maxValue[i-1][j]
                if j > 0:
                    left = maxValue[i][j-1]
                maxValue[i][j] = max(up,left)+grid[i][j]

        return maxValue[rows-1][cols-1]

将二维数组简化为一维数组的代码实现：

class Solution(object):
    def maxValue(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # write code here
        rows = len(grid)
        cols = len(grid[0])
        if grid == [] or rows<=0 or cols<=0:
            return None
        maxValue = [0 for i in range(cols)]
        for i in range(rows): 
            for j in range(cols):
                up = 0
                left = 0
                if i > 0:  #行大于0
                    up = maxValue[j]
                if j > 0:
                    left = maxValue[j-1]
                maxValue[j] = max(up,left)+grid[i][j]

        return maxValue[cols-1]

提交结果：

二维数组的结果 一维数组的结果