DP

这是一个经典的**动态规划（DP）**问题，类似于“数字三角形”或“走方格”，但增加了一个复杂的移动规则：可以向上、向下、向右走，且不能走回头路（不重复经过）。

核心难点

普通的走方格问题通常只能“向右”或“向下”，这样状态转移是单向的，没有后效性。但本题可以“向上”和“向下”走，这意味着在第 $j$ 列，我们可以从第 $j-1$ 列跨过来，然后在第 $j$ 列内部上下移动。

关键性质

由于不能重复经过方格，且列的方向只能向右（不能向左），我们可以得出一个重要结论：在每一列内部，路径必须是单调的（要么一直向下，要么一直向上，或者不垂直移动）。

• 如果路径在第 $j$ 列先向下再向上（例如从 $(k, j)$ 到 $(i, j)$ 其中 $k < i$，然后又回到 $(p, j)$ 其中 $p < i$），那么中间的方格就会被重复经过，这是不允许的。
• 因此，到达 $(i, j)$ 的路径只有三种可能来源：
  1. 直接从左边过来：从 $(i, j-1)$ 走到 $(i, j)$。
  2. 从上面下来：从 $(k, j-1)$ ($k < i$) 走到 $(k, j)$，然后一路向下走到 $(i, j)$。
  3. 从下面上来：从 $(k, j-1)$ ($k > i$) 走到 $(k, j)$，然后一路向上走到 $(i, j)$。

2. 动态规划设计

状态定义

设 $dp[i][j]$ 表示从起点 $(1, 1)$ 走到 $(i, j)$ 所能获得的最大整数之和。

状态转移

我们需要按列递推（$j$ 从 1 到 $m$）。对于第 $j$ 列的每个位置 $(i, j)$，我们需要计算两个辅助值：

• $down[i]$：表示到达 $(i, j)$ 且最后一段是在第 $j$ 列向下走（或刚从左边过来）的最大值。
• $up[i]$：表示到达 $(i, j)$ 且最后一段是在第 $j$ 列向上走（或刚从左边过来）的最大值。

转移方程：

1. 计算 $down$ 数组（从上往下扫）：

   • 对于第 1 行：只能从左边过来。

     $$down[1] = dp[1][j-1] + a[1][j]$$

   • 对于第 $i$ 行 ($i > 1$)：可以从左边直接过来，或者从上面 $(i-1, j)$ 走下来。

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

     解释：$\max(dp[i][j-1], down[i-1])$ 代表了到达 $(i, j)$ 上方的最优路径（无论是横向切入还是纵向延续），加上当前格子的值。

2. 计算 $up$ 数组（从下往上扫）：

   • 对于第 $n$ 行：只能从左边过来。

     $$up[n] = dp[n][j-1] + a[n][j]$$

   • 对于第 $i$ 行 ($i < n$)：可以从左边直接过来，或者从下面 $(i+1, j)$ 走上来。

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

3. 合并结果：

   $$dp[i][j] = \max(down[i], up[i])$$

边界条件与初始化

• 起点：$dp[1][1] = a[1][1]$。
• 第一列：只能从上往下走（因为起点在左上角）。

  $$dp[i][1] = dp[i-1][1] + a[i][1]$$

• 初始值：$dp$ 数组初始化为负无穷（因为题目中有权值为负的情况）。

3. 代码实现 (C++)

#include <iostream>
using namespace std;

// 定义数据范围
const int MAXN = 1005;
const long long INF = 2e18; // 使用 long long 防止溢出，初始值设得足够小

int a[MAXN][MAXN];
long long dp[MAXN][MAXN];
long long down[MAXN]; // 辅助数组：向下走的最优值
long long up[MAXN];   // 辅助数组：向上走的最优值

int main() {

    int n, m;
    cin >> n >> m;

    // 读取矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }

    // 初始化 dp 数组为负无穷
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = -INF;
        }
    }

    // 1. 处理第一列（只能从上往下走）
    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; ++i) {
        dp[i][1] = dp[i-1][1] + a[i][1];
    }

    // 2. 处理后续列
    for (int j = 2; j <= m; ++j) {
        // --- 计算向下走的情况 (down) ---
        // 第1行只能从左边过来
        down[1] = dp[1][j-1] + a[1][j];
        for (int i = 2; i <= n; ++i) {
            // 取“直接从左边过来”和“从上面走下来”的最大值
            down[i] = max(dp[i][j-1], down[i-1]) + a[i][j];
        }

        // --- 计算向上走的情况 (up) ---
        // 第n行只能从左边过来
        up[n] = dp[n][j-1] + a[n][j];
        for (int i = n - 1; i >= 1; --i) {
            // 取“直接从左边过来”和“从下面走上来”的最大值
            up[i] = max(dp[i][j-1], up[i+1]) + a[i][j];
        }

        // --- 合并结果 ---
        for (int i = 1; i <= n; ++i) {
            dp[i][j] = max(down[i], up[i]);
        }
    }

    // 输出右下角的结果
    cout << dp[n][m] << endl;

    return 0;
}

4. 复杂度分析

• 时间复杂度：$O(N \times M)$。我们遍历了每一列，每列内部进行了两次线性扫描（向下和向上），总操作次数与格子总数成正比。对于 $N, M \le 1000$，运算量约为 $10^6$，完全可以在 1 秒内完成。
• 空间复杂度：$O(N \times M)$。存储矩阵和 DP 数组需要约 $10^6 \times 8$ 字节 $\approx 8$ MB，远低于 128MB 的限制。

5. 样例 1 图解

输入：

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

程序运行过程简述：

• Col 1: [1, 3, 1] (累加: 1, 1+2=3, 3-2=1)
• Col 2:
  • down: [0, 2, 4] (例如 down[3] 来自 max(dp[3][1]=1, down[2]=2) + 2 = 4)
  • up: [1, 2, 3]
  • dp: [1, 2, 4] (取 max)
• Col 3:
  • dp: [9, 8, 5] (最大值 9 来自从下方上来的路径)
• Col 4:
  • dp: [11, 10, 9]
• 最终结果: 9。

这与题目样例输出一致。

另一个思路供参考:

#include <iostream>
#include <algorithm>
using namespace std;

long long a[2005][2005];
long long dp[2005][2005];
long long cur[2005];
long long down[2005];
long long up[2005];

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读入矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    
    long long neg_inf = -1e18; // 相当于 -1e18
    
    // 初始化 dp
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = neg_inf;
        }
    }
    
    // 起点
    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) {
        // 从左边列直接右移
        for (int i = 1; i <= n; ++i) {
            if (dp[i][j-1] != neg_inf) {
                cur[i] = dp[i][j-1] + a[i][j];
            } else {
                cur[i] = neg_inf;
            }
        }
        
        // 向下扫描
        for (int i = 1; i <= n; ++i) down[i] = cur[i];
        for (int i = 2; i <= n; ++i) {
            if (down[i-1] != neg_inf) {
                down[i] = max(down[i], down[i-1] + a[i][j]);
            }
        }
        
        // 向上扫描
        for (int i = 1; i <= n; ++i) up[i] = cur[i];
        for (int i = n-1; i >= 1; --i) {
            if (up[i+1] != neg_inf) {
                up[i] = max(up[i], up[i+1] + a[i][j]);
            }
        }
        
        // 合并
        for (int i = 1; i <= n; ++i) {
            dp[i][j] = max(down[i], up[i]);
        }
    }
    
    cout << dp[n][m] << '\n';
    return 0;
}