13518219792
题目：礼物的最大价值
在一个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()
