HDU1619（动态规划记录路径）

 思路：利用动态规划的思想将输入矩阵的dp矩阵记录下来，用结构体来存储dp矩阵，并且将每个元素的前驱结点记录下来。

将所有最小权值路径记录下来，从尾节点到头结点进行回溯，用stk数组记录路径下标，倒序输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=12;
const int maxm=102;
struct node
{int path;int pre;
} dp[maxn][maxm];
struct stak
{int fat[maxm];//存放下标
} stk[maxn];
int mapp[maxn][maxm];
int n,m;
int dir[3],p,maxp,q;
int record[maxn];
bool cmp(stak a,stak b)
{for(int i=0; i<m; i++)if(a.fat[i]==b.fat[i])continue;elsereturn a.fat[i]<b.fat[i];
}
void init()
{memset(dp,0,sizeof(dp));memset(stk,0,sizeof(stk));
}
void design()
{for(int i=0; i<n; i++){dp[i][0].path=mapp[i][0];dp[i][0].pre=i;//父节点是自身}for(int j=1; j<m; j++)for(int i=0; i<n; i++){dir[0]=i-1;dir[1]=i;dir[2]=i+1;for(int k=0; k<3; k++){if(dir[k]<0)dir[k]=(dir[k]+n)%n;else if(dir[k]>=n)dir[k]%=n;}//解决下标越界的问题p=dir[0];maxp=dp[p][j-1].path;//最小值而不是最大值for(int k=0; k<3; k++){q=dir[k];if(maxp>dp[q][j-1].path){maxp=dp[q][j-1].path;p=q;}else if(maxp==dp[q][j-1].path&&q<p){p=q;}}dp[i][j].path=maxp+mapp[i][j];dp[i][j].pre=p;}p=0;maxp=dp[p][m-1].path;int num=0;for(int i=1; i<n; i++){if(maxp>dp[i][m-1].path){p=i;maxp=dp[i][m-1].path;}}//p是最小值的第一个下标for(int i=0; i<n; i++)if(maxp==dp[i][m-1].path){record[num]=i;num++;}//最优路径的个数for(int i=0; i<num; i++)//遍历路径{int pre=record[i];stk[i].fat[0]=pre;for(int j=1; j<m; j++) //一共存储m次下标{pre=dp[pre][m-j].pre;stk[i].fat[j]=pre;}}sort(stk,stk+num,cmp);
}
int main()
{while(~scanf("%d%d",&n,&m)){init();for(int i=0; i<n; i++)for(int j=0; j<m; j++)scanf("%d",&mapp[i][j]);design();for(int i=m-1; i>=0; i--){printf("%d",stk[0].fat[i]+1);if(i)printf(" ");}printf("\n%d\n",maxp);}return 0;
}

推荐学习其他大佬的博客：blog.csdn.net/V5ZSQ/article/details/48877963

总结：1.大佬的博客的优势在于倒着计算dp矩阵，这样在更新二维数组的同时可以解决字典序的问题。

2.程序中用于解决下标越界的语句段可以用更好的形式表达：

            for(int k=0; k<3; k++){dir[k]=(dir[k]+n)%n;}//解决下标越界的问题

3.大佬的博客也给了其他的借鉴：一个位置的前驱结点使用二维数组存储也很方便。如：path[maxn][maxm]