本博客主要內(nèi)容為圖書《劍指offer》第二版47 題的解題思路及代碼。方法可能還有不足之處，歡迎大家討論評論。
1. 題目描述
??在一個 m*n 的棋盤中的每一個格都放一個禮物，每個禮物都有一定的價值（價值大于0）.你可以從棋盤的左上角開始拿各種里的禮物，并每次向左或者向下移動一格，直到到達(dá)棋盤的右下角。給定一個棋盤及上面?zhèn)€的禮物，請計算你最多能拿走多少價值的禮物？
??比如說現(xiàn)在有一個如下的棋盤，
在這個棋盤中，按照（1，12，5，7，7，16，5）的順序可以拿到總價值最大的禮物。
2. 題目分析
??我們首先使用遞歸的思路進(jìn)行分析，當(dāng)求解到達(dá)右下角時禮物的最大總價值時，可以通過如下的遞推關(guān)系進(jìn)行計算
其中 f ( i , j ) 是要求解的最大值， f ( i , j ? 1 ) 到達(dá) ( i , j ) 點左邊點時得到最大禮物價值，而 f ( i ? 1 , j ) 是到達(dá) ( i , j ) 點上邊點時得到最大禮物價值， g ( i , j ) 是 ( i , j ) 點禮物的價值。同歸地推關(guān)系式可以使用遞歸的方法進(jìn)行求解，但是在使用遞歸求解的過程中會重復(fù)求解許多的值，所以這個時候就應(yīng)該使用動態(tài)規(guī)劃的方式進(jìn)行求解。也就是說分析的過程如上，是從上到下遞歸地分析；而求解過程是從下到上循環(huán)地求解。
??一個很直觀的想法是，我們將每一步求解出的結(jié)果都保存在一個矩陣中。那么在這個問題中就要有一個和原始矩陣等大的矩陣進(jìn)行存儲，但是實際上只需要一個與列數(shù)相同維數(shù)的一維數(shù)組就夠了。為什么存儲這么少的就夠了呢。
??在動態(tài)規(guī)劃求解這個問題的時候，我們找出到達(dá)每一行中每個位置的最大值，在求解第一行的時候，很明顯只能一直向右走，對于第二行的一個數(shù)字，很明顯只能從 ( 0 , 0 ) 走到 ( 0 , 1 ) ，這個還是先用與原始矩陣同樣大的矩陣進(jìn)行分析，如下所示
在上圖中，如果要求到達(dá) a 點的禮物的最大值，它只與左邊的值和它上面的值有關(guān)，所以在計算 a 之前就可以將 1 去掉了，因為后面的計算都不會用到 a 的。同理計算出 a 點的最大值之后就可以將 11 替換掉了，因為再求 b 的時候不會再用到。分析到這里我們就可以發(fā)現(xiàn)，并不需要一個與原始矩陣等大的矩陣來存儲中間計算的值，只需要一個與列數(shù)相同的一維向量即可。
3. 代碼實現(xiàn)
class
Solution
:
def
getmaxValue
(self, values, rows, cols)
:
if
not
values
or
rows<=
0
or
cols <=
0
:
return
0
# 用于存放中間數(shù)值的臨時數(shù)組
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
)
參考文獻(xiàn)
- 何海濤. 劍指Offer.第2版[M]. 電子工業(yè)出版社, 2014.
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
