之所以想到要注釋一下，沒別的意思，只是因?yàn)閹讉€(gè)月前剛學(xué)DP，完全看不懂，前幾天費(fèi)了幾個(gè)小時(shí)終于看懂了，注釋下來，能使自己整理一下思路，也作為自己的一篇日記。

當(dāng)時(shí)我能看懂時(shí)間和空間均為O(MN^2)的函數(shù)，但可能由于自己看書是直接從動(dòng)態(tài)規(guī)劃一章看起，書上對(duì)于經(jīng)過優(yōu)化的函數(shù)也沒有更多的解析，當(dāng)時(shí)看起來完全不知所云。前幾天看的時(shí)候，是對(duì)著方程結(jié)合書上的幾句話自己去理解，嘗試自己動(dòng)手去寫，但錯(cuò)了。看書上代碼，都要自己去理解那些變量數(shù)組是干什么用的，感覺也是非常吃力。

1，

我覺得理解那個(gè)優(yōu)化函數(shù)，必須先要充分理解那個(gè)二維的DP方程：

b[i][j]=max(b[i][j-1]+a[j],max(b[i-1][t])+a[j])  (i-1<=t<j)

b[i][j]表示的是第i段在前j項(xiàng)（含第j項(xiàng)）的最大值。對(duì)于b[i][j]含有第j項(xiàng)必須要理解好！則方程的意思是：對(duì)于a[j]項(xiàng)，要么將它加到第i段，要么它自己作為新的一段。

注意到方程外層的max選擇，都要加上a[j]這一項(xiàng)。這里可能很容易產(chǎn)生一個(gè)疑問，如果a[j]是一個(gè)負(fù)數(shù)，為什么還要加上a[j]呢？回到b[i][j]所表示的意義上解釋，由于b[i][j]表示的是含有第j項(xiàng)的最大值，所以a[j]是肯定要加進(jìn)來的。假使a[j]是一個(gè)負(fù)數(shù)，它加進(jìn)來了也不會(huì)影響在第i段中前j-1項(xiàng)的最大值。

所以第m段的最大值，并不是b[m][n]，而是b[m][m~n]之間的最大值。

同樣道理，第i-1段的最大值是b[i-1][t],(i-i<=t<j)。

2，

理解了上述的DP方程后，再來考慮優(yōu)化，正如書上所說的，由于在第i段中，只用到第i段和第i-1段的值。如果采用一維數(shù)組存儲(chǔ)b[]，只要在計(jì)算第i段的時(shí)候，沒有去改變第i-1段保留下來的值即可。再考慮到，內(nèi)層max選擇，需要用到第i-1段在i-1到j(luò)-1位置的最大值，不但要進(jìn)行重復(fù)計(jì)算，也影響到b[j]的計(jì)算，因?yàn)閖前面的值既要用作b[j]的計(jì)算，也要更新作為下一段i+1計(jì)算時(shí)所用。

為了解決這個(gè)問題，書上是利用了一個(gè)輔助的一維數(shù)組c[]，c[j]保存的是上一段i-1在j位置的最大值。顯然計(jì)算第i段在j位置的值b[j]要用到的c[]的下標(biāo)是從i-1到j(luò)-1的。

那么這時(shí)DP方程可以變?yōu)椋?o:p>

b[j]=max(b[j-1]+a[j],c[j-1]+a[j])

要注意，b[j-1]與c[j-1]是相差一段的，即b[j-1]計(jì)算的是第i段的值，而c[j-1]記錄的是i-1段的值。

這里有一個(gè)關(guān)鍵是對(duì)c[]在計(jì)算第i段值b[j]的時(shí)候，要及時(shí)更新，以作計(jì)算下一段使用。

3，

以上的具體實(shí)現(xiàn)自己寫不出來，還是照看書上的代碼，略作解析。其實(shí)明白了上面說明的兩段，書上代碼是很好理解的。書上對(duì)于邊界條件的處理，我覺得做得非常好，而我也正是錯(cuò)在這個(gè)地方。