题目描述给定 n*m的方格每个格子有整数。小熊从左上角(0,0)走到右下角(n‑1,m‑1)。每一步只能向上、向下、向右不能重复经过格子不能越界。求取到格子数字总和的最大值。注意不能向左走一旦走到下一列就再也回不到左边列否则格子会重复访问。也就是说路径一定是按列推进。同一列内部可以上下来回走但是不能回到左侧已经处理完的列。思路一暴力 DFS(25分)直接暴力搜索标记 vis 访问向上 / 下 / 右递归搜索到达终点更新答案。#includebits/stdc.husingnamespacestd;intn,m,maxnINT_MIN;inta[1005][1005];intdx[3]{-1,1,0};intdy[3]{0,0,1};boolvis[1005][1005];voiddfs(intx,inty,intsum){if(xn-1ym-1){maxnmax(maxn,sum);return;}for(inti0;i3;i){intnxxdx[i],nyydy[i];if(nx0nxnny0nym!vis[nx][ny]){vis[nx][ny]true;dfs(nx,ny,suma[nx][ny]);vis[nx][ny]false;}}}intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){cina[i][j];}}vis[0][0]true;dfs(0,0,a[0][0]);coutmaxn;return0;}问题n,m1000网格总共有 10^6个格子DFS 搜索状态爆炸只能过小数据。思路二记忆化 DFS不能向左走只能向上、向下、向右。到达(x,y)的时候我们只需要记录是从哪个方向来到当前格子。from 0从左边(y‑1)向右走过来from 1从上边(x‑1)向下走过来from 2从下边(x1)向上走过来如果是从上方来from1就不能再向上走防止回头重复如果是从下方来from2就不能再向下走防止回头重复。状态定义dp[x][y][from]在(x,y)由from方向抵达走到终点的最大权值和。转移向右走到(y1)来源标记为0如果不是从上方过来可以向上走来源标记2如果不是从下方过来可以向下走来源标记1。#includebits/stdc.husingnamespacestd;intn,m;inta[1005][1005];intdx[3]{-1,1,0};intdy[3]{0,0,1};boolvis[1005][1005][3];longlongdp[1005][1005][3];//记忆化 0左边过来1上面2下面longlongdfs(intx,inty,intfrom){if(xn-1ym-1){returna[x][y];}if(vis[x][y][from])returndp[x][y][from];vis[x][y][from]true;longlongbest-1e18;if(y1m)//向右走{bestmax(best,dfs(x,y1,0));}if(from!1x-10)//向上走{bestmax(best,dfs(x-1,y,2));}if(from!2x1n)//向下走{bestmax(best,dfs(x1,y,1));}dp[x][y][from]a[x][y]best;returndp[x][y][from];}intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){cina[i][j];}}memset(vis,0,sizeof(vis));coutdfs(0,0,0);return0;}这种方法虽然在洛谷里能过但是卡着极限过的。思路三递推 DP(正解)核心性质路径不允许向左走因此处理完第j‑1整列再处理第 j 列。同一列 j 内部可以先从上往下扫一遍再从下往上扫一遍。状态定义:dp[i][j]走到第 i 行第 j 列格子并且结束在(i,j)的最大总和。#includebits/stdc.husingnamespacestd;intn,m;inta[1005][1005];longlongdp[1005][1005];intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){cina[i][j];}}for(inti0;in;i){for(intj0;jm;j){dp[i][j]-1e18;}}dp[0][0]a[0][0];//第一列从上往下走for(inti1;in;i){dp[i][0]dp[i-1][0]a[i][0];}//处理每一列for(intj1;jm;j){//从上往下longlongd[1005];d[0]dp[0][j-1]a[0][j];for(inti1;in;i){d[i]max(dp[i][j-1],d[i-1])a[i][j];}//从下往上longlongu[1005];u[n-1]dp[n-1][j-1]a[n-1][j];for(intin-2;i0;i--){u[i]max(dp[i][j-1],u[i1])a[i][j];}//最大值for(inti0;in;i){dp[i][j]max(d[i],u[i]);}}coutdp[n-1][m-1];return0;}