本博客主要内容为图书《剑指offer》第二版47 题的解题思路及代码。方法可能还有不足之处，欢迎大家讨论评论。
1. 题目描述
在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
比如说现在有一个如下的棋盘，
在这个棋盘中，按照（1，12，5，7，7，16，5）的顺序可以拿到总价值最大的礼物。
2. 题目分析
我们首先使用递归的思路进行分析，当求解到达右下角时礼物的最大总价值时，可以通过如下的递推关系进行计算
其中 f ( i , j ) 是要求解的最大值， f ( i , j − 1 ) 到达 ( i , j ) 点左边点时得到最大礼物价值，而 f ( i − 1 , j ) 是到达 ( i , j ) 点上边点时得到最大礼物价值， g ( i , j ) 是 ( i , j ) 点礼物的价值。同归地推关系式可以使用递归的方法进行求解，但是在使用递归求解的过程中会重复求解许多的值，所以这个时候就应该使用动态规划的方式进行求解。也就是说分析的过程如上，是从上到下递归地分析；而求解过程是从下到上循环地求解。
一个很直观的想法是，我们将每一步求解出的结果都保存在一个矩阵中。那么在这个问题中就要有一个和原始矩阵等大的矩阵进行存储，但是实际上只需要一个与列数相同维数的一维数组就够了。为什么存储这么少的就够了呢。
在动态规划求解这个问题的时候，我们找出到达每一行中每个位置的最大值，在求解第一行的时候，很明显只能一直向右走，对于第二行的一个数字，很明显只能从 ( 0 , 0 ) 走到 ( 0 , 1 ) ，这个还是先用与原始矩阵同样大的矩阵进行分析，如下所示
在上图中，如果要求到达 a 点的礼物的最大值，它只与左边的值和它上面的值有关，所以在计算 a 之前就可以将 1 去掉了，因为后面的计算都不会用到 a 的。同理计算出 a 点的最大值之后就可以将 11 替换掉了，因为再求 b 的时候不会再用到。分析到这里我们就可以发现，并不需要一个与原始矩阵等大的矩阵来存储中间计算的值，只需要一个与列数相同的一维向量即可。
3. 代码实现
class
Solution
:
def
getmaxValue
(self, values, rows, cols)
:
if
not
values
or
rows<=
0
or
cols <=
0
:
return
0
# 用于存放中间数值的临时数组
temp = [
0
] * cols
for
i
in
range(rows):
for
j
in
range(cols):
left =
0
up =
0
if
i >
0
:
up = temp[j]
if
j >
0
:
left = temp[j-
1
]
temp[j] = max(up,left) + values[i*rows+j]
return
temp[-
1
]
s = Solution()
a = s.getmaxValue([
1
,
10
,
3
,
8
,
12
,
2
,
9
,
6
,
5
,
7
,
4
,
11
,
3
,
7
,
16
,
5
],
4
,
4
)
参考文献
- 何海涛. 剑指Offer.第2版[M]. 电子工业出版社, 2014.
