第一次做动规题目，下面均为个人理解以及个人方法，状态转移方程以及状态的定义也是依据个人理解。请过路大神不吝赐教。

状态：每一列的每个数[ i ][ j ]都是一个状态；

然后定义状态[ i ][ j ]的指标函数d[ i ][ j ]为从[ i ][ j ]向右出发的能够得到的最小的整数和；

状态转移方程：d[ i ][ j ]=min(d[ i+1 ][ j+1 ][ i-1 ][ j+1 ][ i ][ j+1 ])+a[ i ][ j ];

当中a[ i ][ j ]为当前位置的数值；

然后有了这些就能够用自己熟悉的方式对问题求解了。

我所知道的合理求解过程有两种：记忆化搜索和递推。

我所知道的输出方法有两种：在求解过程中记录最优位置并在最后输出。全然在输出过程中寻求最佳位置并输出；

下面是自己写的两种输出不同的方法，其处理求解过程均为递推，我觉得对本题来讲记忆化搜索比較复杂，而递推又显而易见

1.

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int m,n;

int a[50][1100];

int rd[50][1100];

ll d[50][1100];

ll min_ans(ll t1,ll t2 ,ll t3)

{

    long long temp=min(t1,t2);

    temp=min(temp,t3);

    return temp;

}

int min_pos(ll ans,int y,int x1,int x2,int x3)

{

    int pos=m+1;

    if(ans==d[x1][y])

    {

        pos=min(pos,x1);

    }

    if(ans==d[x2][y])

    {

        pos=min(pos,x2);

    }

    if(ans==d[x3][y])

    {

        pos=min(pos,x3);

    }

    return pos;

}

void dp()

{

    for(int i=n;i>=1;i--)

    {

        for(int j=1;j<=m;j++)

        {

            int temp1=j-1;

            if(temp1==0) temp1=m;

            int temp2=j+1;

            if(temp2>m) temp2=1;

            ll t1,t2,t3,ans;int pos;

            t1=d[temp1][i+1];t2=d[j][i+1];t3=d[temp2][i+1];

            d[j][i]=min_ans(t1,t2,t3)+a[j][i];

            rd[j][i]=min_pos(d[j][i]-a[j][i],i+1,temp1,j,temp2);

        }

    }

}

void print_ans(int pp)

{

    int cur=1;

    printf("%d",pp);

    while(cur!=n)

    {

        printf(" %d",rd[pp][cur]);

        pp=rd[pp][cur];

        cur++;

    }

}

int main()

{

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        memset(d,0,sizeof(d));

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                scanf("%d",&a[i][j]);

            }

        }

        dp();

        long long min_ = -1;

        for(int i=1;i<=m;i++)

        {

            if(min_==-1) min_=d[i][1];

            else

            min_=min(min_,d[i][1]);

        }

        int pp;

        for(int i=1;i<=m;i++)

        {

            if(d[i][1]==min_)

            {

                pp=i;

                break;

            }

        }

        print_ans(pp);

        printf("\n");

        printf("%lld",d[pp][1]);

        printf("\n");

    }

    return 0;

}

2.

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int m,n;

int a[50][1100];

int rd[50][1100];

ll d[50][1100];

ll min_ans(ll t1,ll t2 ,ll t3)

{

    long long temp=t1>t2?

t2:t1;

    return temp>t3?t3:temp;

}

void dp()

{

    for(int i=n; i>=1; i--)

    {

        for(int j=1; j<=m; j++)

        {

            int temp1=j-1;

            if(temp1==0) temp1=m;

            int temp2=j+1;

            if(temp2>m) temp2=1;

            ll t1,t2,t3,ans;

            int pos;

            t1=d[temp1][i+1];

            t2=d[j][i+1];

            t3=d[temp2][i+1];

            d[j][i]=min_ans(t1,t2,t3)+a[j][i];

        }

    }

}

void print_ans(int pp,int cur)

{

    printf("%d",pp);

    cur++;

    while(1&&cur<=n)

    {

        int i;

        for(i=1; i<=m; i++)

        {

            if((d[i][cur]==d[pp][cur-1]-a[pp][cur-1]))

            {

                if(pp==1&&(i==m||i==pp||i==pp+1))

                {

                    printf(" %d",i);

                    break;

                }

                else if(pp==m&&(i==1||i==pp||i==pp-1))

                {

                    printf(" %d",i);

                    break;

                }

                else if(i>=pp-1&&i<=pp+1)

                {

                    {

                        printf(" %d",i);

                        break;

                    }

                }

                else

                    continue;

            }

        }

        pp=i;

        cur++;

        if(cur>n)

            break;

    }

}

int main()

{

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        memset(d,0,sizeof(d));

        for(int i=1; i<=m; i++)

        {

            for(int j=1; j<=n; j++)

            {

                scanf("%d",&a[i][j]);

            }

        }

        dp();

        long long min_ = -1;

        for(int i=1; i<=m; i++)

        {

            if(min_==-1) min_=d[i][1];

            else

                min_=min(min_,d[i][1]);

        }

        int pp;

        for(int i=1; i<=m; i++)

        {

            if(d[i][1]==min_)

            {

                pp=i;

                break;

            }

        }

        print_ans(pp,1);

        printf("\n");

        printf("%I64d",d[pp][1]);

        printf("\n");

    }

    return 0;

}

第一次做动规题目，花了好久才做好，由于期间出了一些小错误（如今看来依然是一些细节上的错误。与动规无关），并且由于对动规的不熟悉。心里对其也有一点点的恐惧。

可是认定这一道动规并不难，有时自己独立杰出的第一道动规题目。十分想要独立将其AC。然后一直找细节測数据。最终是找到了几处非常不应该犯的细节处理上的错误。这一点让我非常伤心。但最终的AC胜过千言万语。

之后选择还有一种方法，也是磕磕绊绊才写出AC代码orz...

这就算是开了动规吧，多思考多钻研，多学习别人的优秀思路