美文网首页剑指offer- python实现
面试题47:礼物的最大价值

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

作者: 不会编程的程序猿甲 | 来源:发表于2020-03-26 23:54 被阅读0次

题目:

思路:
这道题是动态规划的思想,到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]

提交结果:

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

相关文章

  • 面试题47:礼物的最大价值

    题目 在一个m*n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格...

  • 面试题47:礼物的最大价值

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

  • 面试题47:礼物的最大价值

    在一个mxn的棋盘的每一格斗放油一个礼物,每个礼物都有一定的价值(大于0) 从棋盘的左上角开始,每次可以往右边或者...

  • 47 礼物最大价值

    1.特殊情况,空数组,单行单列单独考虑2.先计算第一行和第一列的dp值,只用累加前面的就可以。3.动态规划计算

  • 面试题47_礼物的最大价值

    题目描述 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上...

  • 面试题47. 礼物的最大价值

    题目描述 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上...

  • 面试题47. 礼物的最大价值

    题目 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开...

  • 剑指 Offer 47. 礼物的最大价值

    剑指 Offer 47. 礼物的最大价值[https://leetcode-cn.com/problems/li-...

  • 剑指 Offer 47 礼物的最大价值

    剑指 Offer 47. 礼物的最大价值[https://leetcode-cn.com/problems/li-...

  • 47. 礼物的最大价值

    47. 礼物的最大价值[https://leetcode.cn/problems/li-wu-de-zui-da-...

网友评论

    本文标题:面试题47:礼物的最大价值

    本文链接:https://www.haomeiwen.com/subject/athkuhtx.html