剑指offer:礼物的最大价值

发布时间:2020-06-18 09:37:42 作者:Jayce_SYSU
来源:网络 阅读:386

题目:礼物的最大价值
在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?
如给定棋盘如下:
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
礼物的最大价值为1+12+5+7+7+16+5=53

# -*- coding: utf-8 -*-
# @Time         : 2019-07-11 9:59
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getMaxValue.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

def getMaxValue(values):
    """
    迷宫类的问题很适合用动态规划来解决,因为前一步的选择影响后一步的进行。
    动态规划的题目一般是从递归思路分析,得到递推公式之后,用循环编码解决,并用数组保存中间结果。

    由于在这个棋盘中只能往右往下走,因此这道题的递推公式为:
    f(i, j) = max(f(i-1, j), f(i, j-1)) + g(i, j)
    其中f(i, j)表示到达坐标为(i, j)的时候最大的值是多少,g(i, j)表示坐标(i, j)自身的值。

    这道题可以用一个和输入等大小的数组来保存中间结果,但是注意到我们计算f(i, j)的时候只需要用到
    f(i-1, j)和f(i, j-1),也就是说i-2及以上的行的值是被忽略的,那么我们就只需要保存第i行的前
    j个元素即可,而第i-1行则只需要保存从下标j开始的元素即从j到col-1.
    综上,我们可以用一个一维数组来保存中间结果,其长度为棋盘的列数(也就是说这个数组长度和棋盘的一
    行一样长)。这个数组前j个元素为f(i, 0), f(i, 1), ..., f(i, j-1),
    后col-j个元素为f(i-1, j), f(i-1, j+1), ..., f(i-1, col-1)

    用图形来表示就是
    xxxxx
    xxooo
    ooMxx
    xxxxx
    其中M为待求最大值的位置,我们这个数组就保存了o表示的这些元素。
    也就是当求M的时候,用它的左边一个和上面一个元素,即左边=maxValue[j-1],右边=maxValue[j]
    """
    if not values or not values[0]:
        return 0

    row, col = len(values), len(values[0])
    maxValues = [0] * col
    for i in range(row):
        for j in range(col):
            up = left = 0
            # 棋盘的第一行和第一列的最大值就是其本身
            if i > 0:
                up = maxValues[j]
            if j > 0:
                left = maxValues[j - 1]
            maxValues[j] = max(up, left) + values[i][j]

    return maxValues[col - 1]

def main():
    values = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]
    print(getMaxValue(values))

if __name__ == '__main__':
    main()
推荐阅读:
  1. 浅谈技术价值
  2. 剑指offer:丑数

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

动态规划

上一篇:NOCC是什么?有什么特点?

下一篇:JavaScript事件委托的原理和使用方法

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》