企业官网建设流程全解析

题目描述

给定 n*m的方格，每个格子有整数。小熊从左上角(0,0)走到右下角(n‑1,m‑1)。每一步只能向上、向下、向右，不能重复经过格子，不能越界。求取到格子数字总和的最大值。
注意：不能向左走！一旦走到下一列，就再也回不到左边列，否则格子会重复访问。也就是说：路径一定是按列推进。同一列内部可以上下来回走，但是不能回到左侧已经处理完的列。

思路一：暴力 DFS(25分)

直接暴力搜索，标记 vis 访问，向上 / 下 / 右递归搜索，到达终点更新答案。

#include<bits/stdc++.h>usingnamespacestd;intn,m,maxn=INT_MIN;inta[1005][1005];intdx[3]={-1,1,0};intdy[3]={0,0,1};boolvis[1005][1005];voiddfs(intx,inty,intsum){if(x==n-1&&y==m-1){maxn=max(maxn,sum);return;}for(inti=0;i<3;i++){intnx=x+dx[i],ny=y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]){vis[nx][ny]=true;dfs(nx,ny,sum+a[nx][ny]);vis[nx][ny]=false;}}}intmain(){cin>>n>>m;for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>a[i][j];}}vis[0][0]=true;dfs(0,0,a[0][0]);cout<<maxn;return0;}

问题：n,m=1000，网格总共有 10^6个格子，DFS 搜索状态爆炸，只能过小数据。

思路二：记忆化 DFS

不能向左走，只能向上、向下、向右。到达(x,y)的时候，我们只需要记录：是从哪个方向来到当前格子。

• from = 0：从左边（(y‑1)，向右走过来）
• from = 1：从上边（(x‑1)，向下走过来）
• from = 2：从下边（(x+1)，向上走过来）

如果是从上方来（from=1），就不能再向上走，防止回头重复；如果是从下方来（from=2），就不能再向下走，防止回头重复。

状态定义：dp[x][y][from]：在(x,y)，由from方向抵达，走到终点的最大权值和。
转移：

向右走到(y+1)，来源标记为0；
如果不是从上方过来，可以向上走，来源标记2；
如果不是从下方过来，可以向下走，来源标记1。

#include<bits/stdc++.h>usingnamespacestd;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(x==n-1&&y==m-1){returna[x][y];}if(vis[x][y][from])returndp[x][y][from];vis[x][y][from]=true;longlongbest=-1e18;if(y+1<m)//向右走{best=max(best,dfs(x,y+1,0));}if(from!=1&&x-1>=0)//向上走{best=max(best,dfs(x-1,y,2));}if(from!=2&&x+1<n)//向下走{best=max(best,dfs(x+1,y,1));}dp[x][y][from]=a[x][y]+best;returndp[x][y][from];}intmain(){cin>>n>>m;for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>a[i][j];}}memset(vis,0,sizeof(vis));cout<<dfs(0,0,0);return0;}

这种方法虽然在洛谷里能过，但是卡着极限过的。

思路三：递推 DP(正解)

核心性质

路径不允许向左走，因此处理完第j‑1整列，再处理第 j 列。同一列 j 内部，可以先从上往下扫一遍，再从下往上扫一遍。
状态定义:dp[i][j]：走到第 i 行第 j 列格子，并且结束在(i,j)的最大总和。

#include<bits/stdc++.h>usingnamespacestd;intn,m;inta[1005][1005];longlongdp[1005][1005];intmain(){cin>>n>>m;for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>a[i][j];}}for(inti=0;i<n;i++){for(intj=0;j<m;j++){dp[i][j]=-1e18;}}dp[0][0]=a[0][0];//第一列：从上往下走for(inti=1;i<n;i++){dp[i][0]=dp[i-1][0]+a[i][0];}//处理每一列for(intj=1;j<m;j++){//从上往下longlongd[1005];d[0]=dp[0][j-1]+a[0][j];for(inti=1;i<n;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(inti=n-2;i>=0;i--){u[i]=max(dp[i][j-1],u[i+1])+a[i][j];}//最大值for(inti=0;i<n;i++){dp[i][j]=max(d[i],u[i]);}}cout<<dp[n-1][m-1];return0;}