当前位置：首页 > news >正文

从NOIP方格取数到双线程DP：解析经典棋盘路径问题的动态规划核心

news 2026/6/28 21:29:17

1. 方格取数问题：从NOIP竞赛到动态规划入门

第一次接触方格取数问题是在准备NOIP比赛的时候，当时看到这个题目就感觉特别有意思。想象一下，你站在一个n×n的棋盘左上角，每次只能向右或向下走，目标是到达右下角。棋盘每个格子里都有一个数字，走过这个格子就能拿到对应的分数。现在问题来了：如果让你走两遍这个棋盘，怎样走才能拿到最多的分数呢？

这个问题看似简单，但仔细想想会发现很多坑。比如，如果两遍都走同样的路径，那么第二次走的时候分数已经被拿走了，就不能重复计算。这就是典型的"双线程"动态规划问题，也是NOIP/NOI竞赛中经常出现的经典题型。

我在初学动态规划时，老师总是强调要找到"最优子结构"和"重叠子问题"。方格取数问题完美体现了这两个特性。最优子结构体现在：到达某个格子的最大分数，取决于之前格子的最优选择；重叠子问题则体现在：两条路径可能会经过相同的中间状态。

2. 从单线程到双线程：DP思维的跃迁

2.1 单路径问题的基本解法

先回忆下单路径问题的解法。假设只要走一遍棋盘，我们可以定义一个二维DP数组：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]

这个状态转移方程非常直观：到达(i,j)点的最大分数，要么来自上方，要么来自左方，取较大值加上当前格子的分数。

我第一次写这个代码时，犯了个典型错误——忘记处理边界条件。当i=1或j=1时，i-1或j-1会越界。后来学会了要么把数组开大一圈，要么单独处理边界情况。

2.2 双路径问题的思维转换

当问题变成两条路径时，情况就复杂多了。最直观的想法是：先走第一条路径，拿走分数后修改棋盘，再走第二条路径。但这样得到的往往不是最优解，因为第一条路径的选择会影响第二条路径的可能性。

正确的做法是同时考虑两条路径。这时候状态定义就需要升级为四维：

dp[i][j][k][l] # 第一条路径到(i,j)，第二条路径到(k,l)时的最大得分

这个思维跳跃很关键——从单独考虑两个过程，转变为同时考虑两个过程的联合状态。这也是双线程DP的核心思想。

3. 四维DP的详细拆解

3.1 状态定义的艺术

定义dp[i][j][k][l]表示：

第一条路径从(1,1)走到(i,j)
第二条路径从(1,1)走到(k,l)
两条路径获得的数字总和最大值

这里有个重要观察：因为每次只能向右或向下走，所以两条路径的步数总是相同的。也就是说，i+j = k+l。这个性质可以帮助我们优化空间复杂度，后面会讲到。

3.2 状态转移方程的推导

状态转移需要考虑四种情况：

第一条路径从上方来，第二条路径从上方来
第一条路径从上方来，第二条路径从左方来
第一条路径从左方来，第二条路径从上方来
第一条路径从左方来，第二条路径从左方来

特别要注意的是，当(i,j)和(k,l)是同一个格子时，分数只能加一次。用代码表示就是：

if i==k and j==l: dp[i][j][k][l] = max(四种情况) + a[i][j] else: dp[i][j][k][l] = max(四种情况) + a[i][j] + a[k][l]

3.3 边界条件的处理

边界处理总是容易出错的地方。对于i,j,k,l=1的情况：

当i=1时，不能从i-1来，只能从j-1来
同理适用于其他维度

在实际编程中，我习惯把dp数组的0行和0列都初始化为0，然后从(1,1)开始计算。这样就不需要特殊处理边界了。

4. 优化技巧：从四维到三维

4.1 利用步数相同的性质

注意到i+j = k+l，我们可以设s = i+j = k+l，这样就把状态降为三维：

dp[s][i][k] # s表示步数，i和k分别表示两条路径的行坐标

列坐标可以通过j = s-i和l = s-k计算得到。

这个优化让空间复杂度从O(n^4)降到了O(n^3)，对于n=10的情况可能差别不大，但当n增大时优势就很明显了。

4.2 滚动数组技巧

进一步优化空间，可以观察到每个状态只依赖于s-1步的状态。所以只需要保存当前步和上一步的两个二维数组即可，空间复杂度降到O(n^2)。

不过在实际比赛中，除非n特别大，否则用三维数组通常就足够了。优化到滚动数组虽然节省空间，但代码可读性会降低，容易出错。

5. 代码实现与调试技巧

5.1 基础四维DP实现

以C++为例，基础实现如下：

int dp[N][N][N][N]; int a[N][N]; // 输入省略... for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) for(int k=1; k<=n; ++k) for(int l=1; l<=n; ++l) { int max_val = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])); if(i==k && j==l) dp[i][j][k][l] = max_val + a[i][j]; else dp[i][j][k][l] = max_val + a[i][j] + a[k][l]; } cout << dp[n][n][n][n];