這題猛然一看像是IOI 94“數(shù)字三角形”，但仔細看上去比“數(shù)字三角形”復雜了許多。
不同之處在于：
1. 數(shù)字三角形中可以以第n行任意一個數(shù)字為起點，而Hill的起點在左下角；
2. 數(shù)字三角形中只可以不停向上走，不可以同行之間走，而此題可以；
3. 此題中可以從一行的一個端點直接繞到另一個端點（同行或上面一行）。
類比數(shù)字三角形，寫出一個遞推式
： d[i][j]=max (d[i][j-1],d[i][j+1],d[i+1][j],d[i+1][j+1]);
無疑這是一種錯誤的寫法，因為出現(xiàn)了環(huán)，對于動態(tài)規(guī)劃有了后效性。
后效性的出現(xiàn)是因為可以同行之間走，但是不會走重復的點是可以肯定的，于是想到后效性是可以消除的。
現(xiàn)在先考慮同行的情況。
假設某一時刻走到了 (i,j) 這一點，在下一步?jīng)Q策的時候，要么是(i,j-1)，要么是(i,j+1)，先不考慮加減之后越界的情況。而如果選擇了(i,j-1)這個點，下一步再決策的時候，勢必不會再重復(i,j)，而只會考慮(i,j-2)。狀態(tài)d[i][j]定義為從(n,1)到點(i,j)的最短距離大小，若d[i][j]來自同行某個數(shù)，只能來自d[i][j-1]或d[i][j+1]其中一個。
于是有了一個基本的思路：
對于每一行來說先向右遞推，再向左遞推，遞推式為
：d[i][j]=min (d[i][j],d[i-1][j]+a[i][j])
向左推的遞推式類似地可以寫出。
每行左右遞推各一次即可，環(huán)的問題根本不需要擔心。d[i][j]必來自于左推和右推時更優(yōu)的一條路，若將d[i][j][0]定義為表示右推的結(jié)果，d[i][j][1]表示左推的結(jié)果，則d[i][j]的最終值為min(d[i][j][0],d[i][j][1])，這樣可能更好理解一點，說明左右互不影響，只是從中選擇一個即可。
循環(huán)進入上一行之后，開始遞推向上走的情況，和數(shù)字三角形遞推式一樣，不過邊緣需要單獨考慮，不再給出
：d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j]
另外說出我在寫程序的時候遇到的一些情況，我要開200萬的long數(shù)組，寫在main()中，沒有成功，提示出錯，我不想用壓縮存儲，看某人的程序把數(shù)組定義為全局，我當時不知道為什么他要那么做，學著設為全局變量（如下），成功了~！在做noip2008第三題的時候也一樣，要開[51][51][51][51]的數(shù)組（當然后來知道可以降一維），開不了，改成全局變量，又成功了~！
以下是我的代碼：
#include<stdio.h>
#define maxint 2000000000
#define min(a,b) (a<b?a:b)
long a[1000][1000]=
{0};
long d[1000][1000]={0};
int main()
{
long n,i,j,k,tmp,x1,x2;
scanf("%ld",&n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%ld",&a[i][j]);//------Read In
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
d[i][j]=maxint;
for(i=0;i<n;i++)
d[n-1][i]=a[n-1][i];
for(i=1;i<n;i++)
d[n-1][i]=d[n-1][i-1]+a[n-1][i];
for(i=n-1;i>=0;i--)
d[n-1][i]=min(d[n-1][i],d[n-1][(i+1)%n]+a[n-1][i]);
for(i=n-2;i>=0;i--)
{
d[i][0]=min(d[i+1][0],d[i+1][1]);
d[i][0]=min(d[i][0],d[i+1][i+1]);
d[i][0]+=a[i][0];
d[i][i]=min(d[i+1][0],d[i+1][i]);
d[i][i]=min(d[i][i],d[i+1][i+1]);
d[i][i]+=a[i][i];
for(j=1;j<=i-1;j++)
d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j];
d[i][0]=min(d[i][0],d[i][i]+a[i][0]);
for(j=1;j<=i;j++)
d[i][j]=min(d[i][j],d[i][j-1]+a[i][j]);
for(j=i;j>=0;j--)
d[i][j]=min(d[i][j],d[i][(j+1)%(i+1)]+a[i][j]);
}
printf("%ld\n",d[0][0]);
return 0;
}