乍一看，这道题似乎与经典递推(dp)过河卒很像。可是仔细看，过河卒中的棋子可以向下或向右，而方格取数中的小熊可以向下、向右，还可以向上。 这意味着什么？ 意味着对于每一个点，小熊可能是从下面过来的，也可能是从上面过来的，如图： 小熊既可以从红色路径抵达灰点，也可以从蓝色路径抵达灰点。 我们不知道小熊抵达某一个点是从上面，下面，或者左边过来的。因此，不能使用过河卒的方法推导。那怎么办呢？ 将储存答案的数组增加一个维度。 设 f[i][j][k] 表示小熊走到 点(i,j)(i,j)(i,j) 时能取到的最大整数和。 其中，kkk表示小熊到达这个点的方式。0表示小熊从这个点的下方过来，1表示小熊从这个点的上方过来。从左边过来的路径单独考虑，不需要专门为其赋一个kkk值。从左边来的路径已经包含在从上方或下方来的路径中。 这样，小熊的路像高架桥一样彼此错落开，路径就显得清晰了。 本题答案较大,要开 LONG LONG 我们采用记忆化搜索的方式，搜索一遍最大值。基本思想如下： 因为要求最大值，所以先将f数组赋值为一个最小值MIN（定义MIN=(-1)*2e18） 题难则反，如果从(1,1)(1,1)(1,1)开始搜索有点困难，那就运用逆向思维，从(n,m)(n,m)(n,m)开始搜索。 初始条件：走到点(1,1)(1,1)(1,1)的最大值只能为a[1][1]。因此，将 f[1][1][0] 和 f[1][1][1] 都赋为a[1][1]。 建立函数 search(int x,int y,int k) ，表示到达以kkk方式到达点(x,y)(x,y)(x,y) 的最大值。 * 若 (x,y)(x,y)(x,y) 超出 nnn x mmm 的方格范围，无解，返回MIN。 * 若 f[x][y][k] 不为MIN（即已经搜索到最大值），返回f[x][y][k]。 * 若k==0（从下方来），那就往下搜索，顺藤摸瓜寻找最大值。此时，小熊可能从下方来，也可能从左边来。而从左边来包含：从左边的上方来，从左边的下方- 来。因此，有三种情况需要搜索并取最大值：从正下方来，从左上方来，从左下方来。 * 若k==1（从上方来），那就往上搜索。同上，有三种情况需要搜索并取最大值：从正上方来，从左上方来，从左下方来。 由此可见，答案即为search(n,m,1)。 （此处k==1是因为(n,m)(n,m)(n,m)只能从上方或左边来，不能从下方来） 因为我们每次都把搜索得到的最大值存在f[x][y][k]，所以每个点都只需要搜一遍，时间复杂度O(nm)O(nm)O(nm)，可以AC。 AC代码 欢迎加入团队

#include <stdio.h> typedef long long LL; const LL min_ll = -1e18; int n, m; LL w[1005][1005], f[1005][1005][2]; inline LL mx(LL p, LL q, LL r) {return p > q ? (p > r ? p : r) : (q > r ? q : r);} inline LL dfs(int x, int y, int from) { if (x < 1 || x > n || y < 1 || y > m) return min_ll; if (f[x][y][from] != min_ll) return f[x][y][from]; if (from == 0) f[x][y][from] = mx(dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y]; else f[x][y][from] = mx(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y]; return f[x][y][from]; } int main(void) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { scanf("%lld", &w[i][j]); f[i][j][0] = f[i][j][1] = min_ll; } f[1][1][0] = f[1][1][1] = w[1][1]; printf("%lld\n", dfs(n, m, 1)); return 0; }

不同于其他题只能走上右或下右，该题能走上下右，单凭普通的dp解决不了问题。 首先，我们思考，只能走右不能走左，意味着我们可以单独将每一列分开求解，而向右走其实是从某列运动到下一列，下一列再运动到下下一列……实质上是一个递推的过程。 然后对于每一列，我们会发现要么只能往上走，要么只能往下走。 为什么呢？ 不能重复经过已经走过的方格。 说明我们不能往上走再往下走，这样就重复走了。同理也不能往下走再往上走。 这样就很好解了，设有两个数组up[i][j]和down[i][j]分别表示从下面走上来到i行j列时的最大值和从上面走下来到i行j列时的最大值。 当然，最大值也有可能是从左边过来的。 再设一个数组f[i][j]代表i行j列最终可取到的最大值。 然后a[i][j]代表i行j列的方格的元素。 所以状态转移方程就可以写出来了： up[i][j]=max(up[i+1][j],f[i][j-1])+a[i][j]; down[i][j]=max(down[i-1][j],f[i][j-1])+a[i][j]; f[i][j]=max(up[i][j],down[i][j]); 发现最大值仅与上一列的最大值有关，所以可以降一维： up[i]=max(f[i],up[i+1])+a[i][j]; down[i]=max(f[i],down[i-1])+a[i][j]; f[i]=max(down[i],up[i]);

小熊从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。 注意：1≤n,m≤1031 \le n,m \le 10^31≤n,m≤103，方格中整数的绝对值不超过 10410^4104,它能取到的整数之和的最大值为 10310^3103* 10310^3103∗*∗10410^4104即101010^{10}1010 所以dp数组定义为long long 类型，不妨所有数组都定义为long long类型。 n行m列格子的值存到a数组 思路1： 从左上角开始搜索，每个格子有三个邻接点，1≤n,m≤1031 \le n,m \le 10^31≤n,m≤103，到右下角 搜索执行次数最多为31063^{10^6}3106，超时！ 思路2: 如果题目是 “只能：往下走 或 往右走“ 为了能从第一行 第一列开始推，可以先把dp数组初始化为极小值，方格中整数的绝对值不超过 10410^4104,它能取到的整数之和的最大值为 $10^3 $* 10310^3103∗*∗10410^4104即101010^{10}1010，极小值为−1010-10^{10}−1010-1 加上向上走会多哪些走法呢？ 因为不能重复经过已经走过的方格，不会出现 走上去 再下来 再上去 这种情况， 向上走到达绿色点处一定是从粉色点走上来的，粉色点又是从当前位置左边或者下边上来的，如上图所示，和上面分析的向右向下类似，即向右向上走。 也正是因为不能重复经过已经走过的方格，所以第一列只能从(1,1）向下走 dp数组第一列一定是从（1,1）向下走得到的， 又因为 每一步只能向上、向下或向右走一格,不会往左走，我们可以一列一列推， 即推到第j列时，前j-1列都推好了。 到达第i行第j列 分成2种情况讨论 ： ①向右向下走到达的； ②向右向上走到达的。 对于第2列~第m列： ①向右向下走 行从1到n ②向右向上走 行从n到1 对于一列来说 向右向下走 和 向右向上走 这一列推出来的值是互不影响的，可以都推完后 (i,j)位置谁推出来的值大就选择谁。 只有一个dp数组 一列中 向右向上走推的时候 会直接覆盖 向右向下走推 的值，没办法2类都推出来比较了。 如何做呢？ 可以再定义2个数组。 j从第2列开始到第m列 对于每一列，i从第1行-->第n行推出 down[i][j]down[i][j]down[i][j] 当第j列的down[][]down[][]down[][]和up[][]up[][]up[][]都推好后，这一列相同位置down[][]down[][]down[][]和up[][]up[][]up[][]比较，dp[i][j]dp[i][j]dp[i][j]为2者最大值。 dp数组第j列就推好了。 整体代码 推完后，dp[n][m]dp[n][m]dp[n][m]就是答案 【参考代码】

#include<bits/stdc++.h> using namespace std; long long n,m; long long a[1005][1005]; long long dp[1005][1005][3]; signed main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=-2147483647; } } dp[1][1][0]=dp[1][1][1]=dp[1][1][2]=a[1][1]; for(int i=2;i<=n;i++){ dp[i][1][1]=dp[i-1][1][1]+a[i][1]; } for(int i=2;i<=m;i++){ for(int j=1;j<=n;j++){ dp[j][i][0]=max(dp[j][i-1][0],max(dp[j][i-1][1],dp[j][i-1][2]))+a[j][i]; if(j>1) dp[j][i][1]=max(dp[j-1][i][0],dp[j-1][i][1])+a[j][i]; } for(int j=n-1;j>=1;j--){ dp[j][i][2]=max(dp[j+1][i][0],dp[j+1][i][2])+a[j][i]; } } cout<<max(dp[n][m][0],max(dp[n][m][1],dp[n][m][2])); return 0; } 个人做法，仅供参考

#include <stdio.h> typedef long long LL; const LL min_ll = -1e18; int n, m; LL w[1005][1005], f[1005][1005][2]; inline LL mx(LL p, LL q, LL r) {return p > q ? (p > r ? p : r) : (q > r ? q : r);} inline LL dfs(int x, int y, int from) { if (x < 1 || x > n || y < 1 || y > m) return min_ll; if (f[x][y][from] != min_ll) return f[x][y][from]; if (from == 0) f[x][y][from] = mx(dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y]; else f[x][y][from] = mx(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y]; return f[x][y][from]; } int main(void) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { scanf("%lld", &w[i][j]); f[i][j][0] = f[i][j][1] = min_ll; } f[1][1][0] = f[1][1][1] = w[1][1]; printf("%lld\n", dfs(n, m, 1)); return 0; }

#include<bits/stdc++.h> using namespace std; long long n,m; long long a[1005][1005]; long long dp[1005][1005][3]; signed main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=-2147483647; } } dp[1][1][0]=dp[1][1][1]=dp[1][1][2]=a[1][1]; for(int i=2;i<=n;i++){ dp[i][1][1]=dp[i-1][1][1]+a[i][1]; } for(int i=2;i<=m;i++){ for(int j=1;j<=n;j++){ dp[j][i][0]=max(dp[j][i-1][0],max(dp[j][i-1][1],dp[j][i-1][2]))+a[j][i]; if(j>1) dp[j][i][1]=max(dp[j-1][i][0],dp[j-1][i][1])+a[j][i]; } for(int j=n-1;j>=1;j--){ dp[j][i][2]=max(dp[j+1][i][0],dp[j+1][i][2])+a[j][i]; } } cout<<max(dp[n][m][0],max(dp[n][m][1],dp[n][m][2])); return 0; }