剑指offer 面试47题

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

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

解题思路：这是一个典型的能用动态规划解决的问题。定义f(i,j)表示到达坐标(i,j)的格子能拿到的礼物总和的最大值。则f(i,j)=max(f(i-1,j),f(i,j-1))+gift(i,j) 利用循环写代码较为高效。

代码一中：利用了一个辅助的二维数组maxValues 有rows行cols列

代码二中，利用一维数组，有cols列(更节省空间)

解题代码：

# -*- coding:utf-8 -*-

class Solution:

    #假设输入array为一维数组，行数为rows,列数为cols,要求输出为最大的那个数值

    def getMaxValue1(self,array,rows,cols):

        # write code here

        if array==[] or rows<=0 or cols<=0:

            return 0

        maxValues=[[0 for i in range(cols)] for j in range(rows)]

        for i in range(rows):

            for j in range(cols):

                left=0

                up=0

                if i>0:

                    #如果行号大于0，说明它上面有数字

                    up=maxValues[i-1][j]

                if j>0:

                    #如果列号大于0，说明它左边有数字

                    left=maxValues[i][j-1]

                maxValues[i][j]=max(up,left)+array[i*cols+j]

        return maxValues[rows-1][cols-1]

    def getMaxValue2(self, array, rows, cols):

        # write code here

        if array == [] or rows <= 0 or cols <= 0:

            return 0

        maxValues=[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

                    up=maxValues[j]

                if j>0:

                    #如果列号大于0，说明它左边有数字。

                    left=maxValues[j-1]

                maxValues[j]=max(up,left)+array[i*cols+j]

        return maxValues[cols-1]

if __name__=="__main__":

    print(Solution().getMaxValue1([1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5],4,4))

    print(Solution().getMaxValue1([15], 1, 1))

    print(Solution().getMaxValue1([1,10,3,8], 1, 4))

    print(Solution().getMaxValue1([1, 10, 3, 8], 4, 1))

    print(Solution().getMaxValue1([],5,5))

    print(Solution().getMaxValue2([1, 10, 3, 8, 12, 2, 9, 6, 5, 7, 4, 11, 3, 7, 16, 5], 4, 4))

    print(Solution().getMaxValue2([15], 1, 1))

    print(Solution().getMaxValue2([1,10,3,8], 1, 4))

    print(Solution().getMaxValue2([1, 10, 3, 8], 4, 1))

    print(Solution().getMaxValue2([],5,5))