剑指offer：礼物的最大价值

剑指offer：礼物的最大价值

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

[微信提示：高防服务器能助您降低 IT 成本，提升运维效率，使您更专注于核心业务创新。

[图文来源于网络，不代表本站立场，如有侵权，请联系高防服务器网删除]
[