A37. CSP-J 2020 方格取数 C++ 题解

---

问题分析

这是一个二维网格上的动态规划问题，但与常规的只能向右/向下走的网格路径问题不同，小熊可以向上、向下或向右走，且不能重复经过已经走过的方格。这意味着：

1. 不能向左走，保证了路径的单向性
2. 每一列最多只能访问一次（因为不能重复）
3. 从左上角(1,1)到右下角(n,m)的路径需要考虑上下移动的可能性

核心思路

动态规划状态定义

设 dp[i][j] 表示从起点(1,1)到达位置(i,j)的最大分数。

然而，由于可以上下移动，简单的二维DP无法处理：当计算dp[i][j]时，可能需要来自dp[i-1][j]（上方）或dp[i+1][j]（下方）的值，这会导致循环依赖。

关键观察

1. 由于只能向右、向上、向下走，不能向左走，因此到达第j列的某个位置时，只能来自：

   • 同一列的上方或下方（上下移动）
   • 左边一列（向右移动）

2. 列间独立性：从第j-1列到第j列时，我们可以先在第j-1列内上下移动获取该列的最佳路径，然后一次性向右移动到第j列。

算法设计

1. 对每一列j，计算从上一列到达本列每个位置的最大值
2. 对于每一列，分别计算：
   • 从上往下扫描的最大值（考虑从上方来的路径）
   • 从下往上扫描的最大值（考虑从下方来的路径）
3. 取两者中的较大值作为该位置的DP值

状态转移方程

对于第j列（j ≥ 2）：

从上往下	从下往上	最终
top[i] = max(dp[i][j-1], top[i-1]) + a[i][j]	bottom[i] = max(dp[i][j-1], bottom[i+1]) + a[i][j]	dp[i][j] = max(top[i], bottom[i])

其中a[i][j]是位置(i,j)的数值。

---

完整代码实现（all AC ，可放心食用）

#include <bits/stdc++.h>
using namespace std;

int main() {
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);

    int n, m;
    scanf("%d%d",&n,&m);
    
    vector<vector<long long>> a(n + 1, vector<long long>(m + 1));
    vector<vector<long long>> dp(n + 2, vector<long long>(m + 2, LLONG_MIN));
    
    // 读取输入数据
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    // 初始化第一列
    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) {
        dp[i][1] = dp[i-1][1] + a[i][1];
    }
    
    // 动态规划处理后续列
    for (int j = 2; j <= m; j++) {
        // 从上往下计算
        vector<long long> top(n + 2, LLONG_MIN);
        top[0] = LLONG_MIN;
        for (int i = 1; i <= n; i++) {
            long long fromLeft = dp[i][j-1];
            long long fromTop = (i > 1) ? top[i-1] : LLONG_MIN;
            top[i] = max(fromLeft, fromTop) + a[i][j];
        }
        
        // 从下往上计算
        vector<long long> bottom(n + 2, LLONG_MIN);
        bottom[n+1] = LLONG_MIN;
        for (int i = n; i >= 1; i--) {
            long long fromLeft = dp[i][j-1];
            long long fromBottom = (i < n) ? bottom[i+1] : LLONG_MIN;
            bottom[i] = max(fromLeft, fromBottom) + a[i][j];
        }
        
        // 取两者中的最大值
        for (int i = 1; i <= n; i++) {
            dp[i][j] = max(top[i], bottom[i]);
        }
    }
    
    // 输出结果
    cout << dp[n][m] << endl;
    
    return 0;//不忘好习惯，歇菜
}

代码解析

1. 数据存储

• a[i][j]：存储网格中的数值
• dp[i][j]：存储到达位置(i,j)的最大分数

2. 初始化

• 起点(1,1)的分数就是a[1][1]
• 第一列只能从上到下走，所以dp[i][1] = dp[i-1][1] + a[i][1]

3. 列处理核心逻辑

对于每一列j（从第2列开始）：

• 从上往下扫描：计算从上方路径来的最大分数
• 从下往上扫描：计算从下方路径来的最大分数
• 每个位置取两者中的最大值

4. 时间复杂度

• 时间复杂度：O(n × m)，需要遍历每个格子
• 空间复杂度：O(n × m)，可以优化到O(n)但代码会更复杂

示例分析

样例

输入：

3 4
1 -1 3 2
2 -1 -1 -4
-2 2 -3 1

处理过程：

1. 第一列：只能从上到下，分数为[1, 3, 1]
2. 第二列：考虑上下移动，得到最佳路径
3. 最终到达(3,4)的最大分数为9

输出：

9

注意事项

1. 数据类型：使用long long防止整数溢出，因为分数可能很大
2. 初始化：使用LLONG_MIN表示不可达状态
3. 边界处理：注意数组下标从1开始，方便处理边界
4. 不能重复：算法自然保证了不重复访问，因为每列只处理一次

算法优化

对于空间要求更高的场景，可以优化到O(n)空间：

• 只保存当前列和前一列的DP值
• 使用两个一维数组滚动更新

但这种优化会使代码复杂度增加，对于比赛通常不需要。

---

总结

这道题的关键在于发现列间的独立性，以及通过上下两次扫描解决同一列内的上下移动问题。这种"双向扫描"的技巧在很多动态规划问题中都有应用，特别是在有方向限制的网格路径问题中。

掌握了这个思路后，类似的问题如"双向路径最大和"、"有方向限制的网格DP"都可以用类似方法解决。

蒜鸟蒜鸟，睡了