傳紙條是一道典型的多進(jìn)程動(dòng)態(tài)規(guī)劃題，四維狀態(tài)的狀態(tài)定義很容易想到，具體定義如下：d[i1,j1,i2,j2]表示第一次從起點(diǎn)走到(i1,j1)這個(gè)點(diǎn)，第二次從起點(diǎn)走到(i2,j2)這個(gè)點(diǎn)所獲得的最大值。狀態(tài)轉(zhuǎn)移方程也很容易寫出：

d[i1,j1,i2,j2]=max(d[i1-1,j1,i2-1,j2],d[i1-1,j1,i2,j2-1],d[i1,j1-1,i2-1,j2],d[i1,j1-1,i2,j2-1])+a[i1,j1]+a[i2,j2]；if i1=i2 and j1=j2 then d[i1,j1,i2,j2]=d[i1,j1,i2,j2]-a[i1,j1]；

關(guān)于這一點(diǎn)在本空間的博客中已經(jīng)提到。

但是這樣的狀態(tài)定義卻重復(fù)計(jì)算了許多子問題。遞推需要四層循環(huán)，前兩層是固定了第一次的終點(diǎn)，然后開始推第二次的終點(diǎn)；試想第一次走到(i,j)這個(gè)點(diǎn)，遞推完成，下次遞推第一次走到(i,j+1)這個(gè)點(diǎn)的情況，即將第二次走到的位置從(1,1)推到(m,n)。直觀地去想，這樣做是不是多出了許多運(yùn)算？或者是沒有充分利用重疊子問題？

發(fā)現(xiàn)對于一個(gè)m,n的矩陣，共有m+n-1條對角線，而每次走下一步，都是從一條對角線，走到下一條對角線。于是有了一個(gè)另外一個(gè)狀態(tài)定義：d[i,j,k]表示在第i條對角線上，第一次走到行坐標(biāo)為j的位置，第二次走到行坐標(biāo)為k的位置。這樣的定義就避免了重復(fù)計(jì)算，因?yàn)樵诘?/span>i條對角線的情況只取決于第i-1條對角線的情況，不需要從頭開始重新計(jì)算，可以想象一下這樣定義的程序執(zhí)行過程。而且可以用滾動(dòng)數(shù)組優(yōu)化空間，最終只需要d[2,51,51]的空間就足夠了！和之前d[51,51,51,51]的空間復(fù)雜度好太多了。在時(shí)間上也是一個(gè)極大的優(yōu)化，最終全部數(shù)據(jù)加在一起會在0.2s內(nèi)解決，之前需要1.9s左右。

以下是我的代碼：

#include<stdio.h>
#define max(a,b) (a>b?a:b)
long m,n,a[51][51],d[2][51][51]={0};
long begin(long x)
{
    if(x>=1&&x<=n) return 1;
    if(x>n&&x<=n+m-1) return x-n+1;
}
long end(long x)
{
    return (x<m?x:m);
}
int main()
{
    freopen("message.in","r",stdin);
    freopen("message.ans","w",stdout);
    long i,j,k;
    scanf("%ld%ld",&m,&n);
    for(i=1;i<=m;i++)
      for(j=1;j<=n;j++)
        scanf("%ld",&a[i][j]);
    for(i=1;i<=n+m-1;i++)
      for(j=begin(i);j<=end(i);j++)
        for(k=begin(i);k<=end(i);k++)
        {
           d[i%2][j][k]=max(d[(i-1)%2][j][k],d[(i-1)%2][j-1][k]);
           d[i%2][j][k]=max(d[i%2][j][k],d[(i-1)%2][j][k-1]);
           d[i%2][j][k]=max(d[i%2][j][k],d[(i-1)%2][j-1][k-1]);
           d[i%2][j][k]+=a[j][i-j+1]+a[k][i-k+1];
           if(j==k)
             d[i%2][j][k]-=a[j][i-j+1];
        }
    printf("%ld\n",d[(n+m-1)%2][m][m]);
return 0;
}