之所以想到要注釋一下，沒別的意思，只是因?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è)地方。
int MaxSum(int m,int n,int *a)
{
if(n<m||m<1) return 0;
int *b=new int[n+1]; //b[j]保存的是第i段中在前j（含j）項(xiàng)的最大值
int *c=new int[n+1]; //c[j]保存的是i-1段中在i-1到j(luò)（含j）項(xiàng)中的最大值
//注意，以上b[j]和c[j]都是指在計(jì)算第i段時(shí)的值；
b[0]=0;
c[1]=0; //第0段時(shí)的兩個(gè)值，初始化邊界條件
for(int i=1;i<=m;i++) //i為當(dāng)前計(jì)算段數(shù)
{
b[i]=b[i-1]+a[i]; //b[i]即b[j]在j=i時(shí)的值，由于j=i，每一個(gè)項(xiàng)都要成為一段，這就是邊界條件
c[i-1]=b[i]; //這里很繞，其實(shí)這句是沒用的，因?yàn)樵诘趇段中數(shù)組c[]保存的值是為下一
//段i+1服務(wù)的，i+1段只用到c[i]，可以直接刪掉，免得誤導(dǎo)
int max=b[i]; //max記錄第i段的從i位置開始所有能用到的項(xiàng)的最大值
for(int j=i+1;j<=i+n-m;j++)
{
b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];//這里用到的c[j-1]
//是沒被修改的，還是上一段i-1中在j-1位置的最大值
c[j-1]=max; //用完后就要修改為第i段中在j-1位置的最大值，明顯，max是記錄了第i段中的
if(max<b[j]) //在j-1位置的最大值，盡管當(dāng)前循環(huán)中計(jì)算的是第j項(xiàng)
max=b[j]; //更新max的值
}
c[i+n-m]=max; //由于max記錄的項(xiàng)總比循環(huán)的j項(xiàng)小1，所以第i段在最后一項(xiàng)中的最大值放在循環(huán)外更新
}
int sum=0; //默認(rèn)全是負(fù)數(shù)的時(shí)候，最大值是0,如果要計(jì)算負(fù)的最大值，可以將sum設(shè)為一個(gè)大負(fù)數(shù)
for(int j=m;j<=n;j++) //為什么還有一次循環(huán)找最大值，而不是直接使用b[n]呢？因?yàn)閎[j]包含了a[j]，
if(sum<b[j]) //在b[j]的值不一定比不包含a[j]的其他項(xiàng)大。
sum=b[j];
return sum;
}
附：pku 2479就是一題求最大2段和。