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