阶段很明显即走到第几列 ;
状态：走到第i列j行，d[i][j] 表示至少还要经过的整数，便是求d[i]中的最小解;
决策：三种走法;
决策选择：选d[i][j]最小的那个
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100+5;
int G[maxn][maxn],d[maxn][maxn];
int main()
{int m,n;while(scanf("%d%d",&m,&n)==2&&m){for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>G[i][j];int first,ans=(1<<30),next[maxn][maxn];for(int j=n-1;j>=0;j--) //倒数第一列开始 for(int i=0;i<m;i++) {if(j==n-1) d[i][j]=G[i][j];else{int go[]={i,i+1,i-1};if(go[1]==m) go[1]=0;if(go[2]==-1) go[2]=m-1;sort(go,go+3);d[i][j]=(1<<30);for(int k=0;k<3;k++)if(d[i][j]>d[go[k]][j+1]+G[i][j]) d[i][j]=d[go[k]][j+1]+G[i][j],next[i][j]=go[k];}if(j==0&&ans>d[i][j]) ans=d[i][j],first=i; //记录第一列中最大的 }printf("%d",first+1);for(int i=next[first][0],j=1;j<n;i=next[i][j],j++)printf(" %d",i+1);printf("\n%d\n",ans);}return 0;
}