题目: 礼物的最大价值
在一个 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()
来源: http://www.bubuko.com/infodetail-3120691.html