这题猛然一看像是IOI 94“数字三角形”，但仔细看上去比“数字三角形”复杂了许多。
不同之处在于：
1. 数字三角形中可以以第n行任意一个数字为起点，而Hill的起点在左下角；
2. 数字三角形中只可以不停向上走，不可以同行之间走，而此题可以；
3. 此题中可以从一行的一个端点直接绕到另一个端点（同行或上面一行）。
类比数字三角形，写出一个递推式
： d[i][j]=max (d[i][j-1],d[i][j+1],d[i+1][j],d[i+1][j+1]);
无疑这是一种错误的写法，因为出现了环，对于动态规划有了后效性。
后效性的出现是因为可以同行之间走，但是不会走重复的点是可以肯定的，于是想到后效性是可以消除的。
现在先考虑同行的情况。
假设某一时刻走到了 (i,j) 这一点，在下一步决策的时候，要么是(i,j-1)，要么是(i,j+1)，先不考虑加减之后越界的情况。而如果选择了(i,j-1)这个点，下一步再决策的时候，势必不会再重复(i,j)，而只会考虑(i,j-2)。状态d[i][j]定义为从(n,1)到点(i,j)的最短距离大小，若d[i][j]来自同行某个数，只能来自d[i][j-1]或d[i][j+1]其中一个。
于是有了一个基本的思路：
对于每一行来说先向右递推，再向左递推，递推式为
：d[i][j]=min (d[i][j],d[i-1][j]+a[i][j])
向左推的递推式类似地可以写出。
每行左右递推各一次即可，环的问题根本不需要担心。d[i][j]必来自于左推和右推时更优的一条路，若将d[i][j][0]定义为表示右推的结果，d[i][j][1]表示左推的结果，则d[i][j]的最终值为min(d[i][j][0],d[i][j][1])，这样可能更好理解一点，说明左右互不影响，只是从中选择一个即可。
循环进入上一行之后，开始递推向上走的情况，和数字三角形递推式一样，不过边缘需要单独考虑，不再给出
：d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j]
另外说出我在写程序的时候遇到的一些情况，我要开200万的long数组，写在main()中，没有成功，提示出错，我不想用压缩存储，看某人的程序把数组定义为全局，我当时不知道为什么他要那么做，学着设为全局变量（如下），成功了~！在做noip2008第三题的时候也一样，要开[51][51][51][51]的数组（当然后来知道可以降一维），开不了，改成全局变量，又成功了~！
以下是我的代码：
#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;
}