A37.方格取数解析+代码

A37.[CSP-J 2020] 方格取数解析

这是一道dp题，本题需要注意一下几点：
1.小熊可以往三个方向（上、右、下）；
2.本题存在负数；

尤其是第一点，这意味着小熊可以有下图的走法：

此时，目标点就会被更新两次。对比之前只有两个方向（右、下）的dp，本题第一次查找到目标点时，我们不能立刻确定目标点是否为最大值。

答案代码（c++语言）：

//acgo A37.[CSP-J 2020] 方格取数 
//难度：绿  解法：dp
#include<bits/stdc++.h>
#define mxx(a,b,c) max(a,max(b,c))
using namespace std;
long long n,m,a[1010][1010];
long long dp[1010][1010][3];
int main(){
	memset(dp,-0x3f,sizeof(dp));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[1][1][0]=a[1][1];
	dp[1][1][1]=a[1][1];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			dp[j-1][i][0]=a[j-1][i]+max(dp[j][i][0],dp[j][i][1]);
			dp[j][i+1][1]=a[j][i+1]+mxx(dp[j][i][0],dp[j][i][1],dp[j][i][2]);
			dp[j+1][i][2]=a[j+1][i]+max(dp[j][i][1],dp[j][i][2]);
		}
		for(int j=n;j>=1;j--){
			dp[j-1][i][0]=a[j-1][i]+max(dp[j][i][0],dp[j][i][1]);
			dp[j][i+1][1]=a[j][i+1]+mxx(dp[j][i][0],dp[j][i][1],dp[j][i][2]);
			dp[j+1][i][2]=a[j+1][i]+max(dp[j][i][1],dp[j][i][2]);
		}
	}
	cout<<mxx(dp[n][m][0],dp[n][m][1],dp[n][m][2]);
}

我们分段拆解。

long long dp[1010][1010][3];

想必各位都能看懂前面的dp[1010][1010]，但后面的为什么还有个[3]呢？

题目中说不能重复经过已经走过的方格。因为小熊不会向左走，所以只要不走上一次走的格子，就不会走回头路（不理解的再想想）。这个[3]就是用来记录上一次时怎么走的，dp[i][j][0]表示上一步往下时， $(i,j)$ 格子的路径最大值；dp[i][j][1]表示上一步往右；dp[i][j][2]表示上一步往下。

    memset(dp,-0x3f,sizeof(dp));

因为本题存在负数，所以如果dp数组初值为 $0$，则在答案为负数时会因为要取最大值而输出0。memset是c++的一种给数组赋值的函数。0x3f在memset里代表极大值，具体为 $1061109567$ （ $16$ 进制下的 $3F3F3F3F$ ）。

	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			dp[j-1][i][0]=a[j-1][i]+max(dp[j][i][0],dp[j][i][1]);
			dp[j][i+1][1]=a[j][i+1]+mxx(dp[j][i][0],dp[j][i][1],dp[j][i][2]);
			dp[j+1][i][2]=a[j+1][i]+max(dp[j][i][1],dp[j][i][2]);
		}
		for(int j=n;j>=1;j--){
			dp[j-1][i][0]=a[j-1][i]+max(dp[j][i][0],dp[j][i][1]);
			dp[j][i+1][1]=a[j][i+1]+mxx(dp[j][i][0],dp[j][i][1],dp[j][i][2]);
			dp[j+1][i][2]=a[j+1][i]+max(dp[j][i][1],dp[j][i][2]);
		}
	}

终于，我们看到了dp的主要代码。

第一步就十分重要，我们必须先列后行。我随便造一个数据（并非随便）：

3 4
0   0   0    0
999 999 -999 0
0   0   -999 0

此时，答案应为1998。但如果按照先行后列，则会输出999。这是因为先行后列时，第二行的999无法重新改变第一行已经计算完成的结果。

接下来，注意到代码中有两个循环变量为j的for循环 ，一个从 $1 \rightarrow n$，一个从 $n \rightarrow 1$。这是为什么呢？

还是用我上面的数据。如果用正常死路思路，只有一个从 $1 \rightarrow n$ 的循环，那么还是会输出999。这还是因为当我们遍历到第二行的999时，第一行的结果已经计算完成了。而再来一个 $n \rightarrow 1$ 的循环，就会把下面的结果重新计算并传到上面（我解释不清楚，你们自己理解吧）。

最后，看for循环内部的代码：

			dp[j-1][i][0]=a[j-1][i]+max(dp[j][i][0],dp[j][i][1]);
			dp[j][i+1][1]=a[j][i+1]+mxx(dp[j][i][0],dp[j][i][1],dp[j][i][2]);
			dp[j+1][i][2]=a[j+1][i]+max(dp[j][i][1],dp[j][i][2]);

这里mxx是我自定义的函数，c++库 里面没有，是在3个数里面取最大值的意思。

根据我上面说的dp数组的意思，可以得知这三行是什么意思。
第一行计算往下走的最大值；第二行计算往右走的最大值；第三行计算往下走的最大值。因为是最大值，所以要用max（上面的mxx本质上也是max）来计算。注意，代码是先列后行。

好了，以上就是代码部分的解析，还有一部分细节：
1.答案可能很大，必须使用long long类型；
2.题解写的十分不容易，代码只打了1小时，题解写了4小时。所以，能不能给一个_小小的点赞呢。

最后的最后，我sqrt2祝各位马年买宝马（本题解写于2026/2/7）。就算不是马年，也能买宝马。