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

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]；

關于這一點在本空間的博客中已經提到。

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

發現對于一個m,n的矩陣，共有m+n-1條對角線，而每次走下一步，都是從一條對角線，走到下一條對角線。于是有了一個另外一個狀態定義：d[i,j,k]表示在第i條對角線上，第一次走到行坐標為j的位置，第二次走到行坐標為k的位置。這樣的定義就避免了重復計算，因為在第i條對角線的情況只取決于第i-1條對角線的情況，不需要從頭開始重新計算，可以想象一下這樣定義的程序執行過程。而且可以用滾動數組優化空間，最終只需要d[2,51,51]的空間就足夠了！和之前d[51,51,51,51]的空間復雜度好太多了。在時間上也是一個極大的優化，最終全部數據加在一起會在0.2s內解決，之前需要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;
}