一道C语言棋盘最优路径的题目，求教

这题还是有点意思的。正如diordna所说，因为涉及到全局最优，大小又是1000x1000，感觉广搜有点困难，所以打算试试DP。。

思路如下不知道对不对。。

Part.1设map[i][j]保存棋盘格子的价值(i=0..n-1,j=0..m-1)设f[i][j][k]记录棋盘(i,j)位置的最大价值和(i=0..n-1,j=0..m-1,k=0,1,2)k表示这个位置是怎么来的：k=0:左→右k=1:上→下k=2:下→上首先初始化f[i][j][k]=-inf然后根据题意有：f[0][0][k]=map[0][0],k=0,1,2

Part.2又因为不能向左走，实际上就是说第j=0列的格子只能向下走所以可以先把f[i][0][1]算出来f[i][0][1]=max(k=0,1){f[i-1][0][k]}+map[0][j]=f[i-1][0][1]+map[i][0],i=1..n-1

Part.3然后考虑任意一个非第0列的格子(i,j),i=0..n-1,j=1..m-1便于思考特殊化一下，假设考虑第j=1列（当然其它列也一样），任意一个格子有3种到达方式，分别对应k=0,1,2但此时我们只知道每个格子的左边格子里的f值那么我们先计算k=0时刻各格子的f值(左→右)f[i][j][0]=max(k=0,1,2){f[i][j-1][k]}+map[i][j],i=0..n-1,j=1

Part.4这样一来各个格子从左边来到后的总价值f就得到了接下来处理从上到下和从下到上的情况由于从某个格子开始一旦选择从上到下或从下到上走后就无法回头了不妨从上到下开始：f[i][j][1]=max(k=0,1){f[i-1][j][k]}+map[i][j],i=1..n-1,j=1然后从下到上：f[i][j][2]=max(k=0,2){f[i+1][j][k]}+map[i][j],i=n-2..0,j=1

Part.5这样一来每个格子对应的3种走法的价值最大值就能得到了如此回到Part.3循环列j=1..m-1

最后只要取max(k=0,1){f[n-1][m-1][k]}即可得到最优路径价值和

试着写了一下，不知道能不能过。。

注意由于开了1000x1000的long数组，所以VC调试的时候注意把堆栈开大一点

#includeusingnamespacestd;#defineMAXN1000#defineINF0x7ffffffflongmap[MAXN][MAXN];longf[MAXN][MAXN][3];longgetmax(longa,longb){return(a>b)?a:b;}voidinit(){for(inti=0;i>n>>m;init();for(inti=0;i>map[i][j];}}f[0][0][0]=f[0][0][1]=f[0][0][2]=map[0][0];//Part.2for(inti=1;i=0;i--){longmax=getmax(f[i+1][j][0],f[i+1][j][2]);if(max==-INF)continue;f[i][j][2]=max+map[i][j];}}cout<<getmax(f[n-1][m-1][0],f[n-1][m-1][1])<<endl;return0;}