发现这道题标签是dp,那就用dp吧

看到这题，本来想用深搜的，但是题目标签迫使我用dp
先讲一下dp思路：

第一步：先抓核心规则，找到「阶段」（最关键的一步）

DP 的本质是无后效性：未来的决策，只和当前状态有关，和怎么走到当前状态的无关。
而「阶段」就是保证无后效性的核心：阶段只能单向推进，算完一个阶段就彻底定型，后面不会回头修改。

找阶段的方法：找题目里的 “不可逆规则”。

• 这道题规则：只能向上、向下、向右走，不能向左走。
• 不可逆推论：列号 j 只会越来越大，一旦走到第 j 列，永远不会回到 j-1 列。
• 结论：列就是天然的阶段。我们从左到右一列一列算，算完第 j 列，它的所有值就固定了，后面第 j+1 列只会用它，不会改它。

很多人 DP 写乱，根源就是上来就定义状态，没先找阶段。阶段找对了，后面就顺了。
反过来：如果你发现算后面的状态时，需要回头改前面已经算过的值，那基本就是阶段划分错了。

---

第二步：定义状态，遵循「最小够用」原则

状态定义的目标：用最少的维度，精确描述 “当前走到哪了”，并且能支撑后续所有转移。

怎么想状态？

先问自己：要算最终答案，我需要知道哪些信息？

• 最终要走到右下角 (n,m) 的最大和。
• 走到任意一个格子 (i,j) 时，我们只关心 “到这里的最大和是多少”，不关心 “是从哪个方向来的”。
• 所以最朴素的状态就是 dp[i][j]：走到 (i,j) 的最大数值和。

为什么不加第三维 “方向”？

最开始加了第三维方向，这是很常见的 “过度设计”。

• 方向的作用，只是为了推导转移；
• 如果我们能通过遍历顺序天然保证转移的合法性，就不需要把方向放进状态里。
• 状态维度越少，转移越简单，越不容易错，复杂度也越低。

检验：是否满足无后效性？

后面的列要用到 dp[i][j] 时，只需要这个最大值本身，不需要知道你是从上、下、左哪个方向过来的。满足，所以这个状态定义是合格的。

---

第三步：推导转移，用「逆向思维」更清晰

转移不要想 “我现在能去哪”，要想**“我这个状态，能从哪些合法的地方来”**。逆向思考不容易漏情况。

先列所有合法来路

对于 dp[i][j]，走到这里只有三种可能：

1. 从左边 (i, j-1) 向右走一步来；
2. 从上面 (i-1, j) 向下走一步来；
3. 从下面 (i+1, j) 向上走一步来。

然后发现问题：同一列的上下转移不能直接混着算

如果直接写：

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

会出大问题：

• 你用 dp[i-1][j] 更新了 dp[i][j]，又用 dp[i][j] 去更新 dp[i+1][j]，相当于路径在同一列里一直往下走，这没问题；
• 但同时你又要从下往上更新，用 dp[i+1][j] 更新 dp[i][j]，就会出现来回走、重复累加同一个格子数值的情况，违反 “不能重复经过格子” 的规则。

解决技巧：拆分「进入列」和「列内单向移动」

这是一个非常经典的处理手法：
既然同一列里可以上下走，但不能来回走，那我们就基于同一个 “入口值”，分别计算两种单向路径。

1. 先算 “入口值”：每个格子从左边走过来的值 left[i] = dp[i][j-1] + a[i][j]。
   这是进入当前列的初始值，只和前一列有关，和当前列其他格子无关。
2. 再算 “只向下走”：从上到下扫，down[i] = max(left[i], down[i-1] + a[i][j])。
   含义：要么直接从左边进入 i 行，要么从 i-1 行向下走过来。
3. 再算 “只向上走”：从下到上扫，up[i] = max(left[i], up[i+1] + a[i][j])。
   含义：要么直接从左边进入 i 行，要么从 i+1 行向上走过来。
4. 合并：dp[i][j] = max(down[i], up[i])。

为什么这样就不会重复？
down 和 up 都是独立基于 left 计算的，互相不引用对方的结果，各自都是单向路径，不会在列里来回绕。
这就保证了：同一列里，每个格子的数值只会被加一次。

---

第四步：边界与初始化，堵死所有不合法路径

这一步很容易被忽略，但负权题目里错一步全错。

思考两个问题

1. 起点是什么？
   左上角 (1,1) 是唯一出发点，所以 dp[1][1] = a[1][1]。
2. 不合法的路径怎么处理？
   很多格子一开始是走不到的，比如第 2 列第 5 行，在没算之前是不合法的。
   因为格子有负数，不能用 0 初始化，必须设成足够小的负数（负无穷），这样取 max 的时候，不合法路径自动被淘汰。

特殊边界单独处理

第 1 列没有左边的列，只能从起点一路向下走，所以单独从上到下累加即可，不需要走完整的列内逻辑。

---

第五步：复杂度校验，确保能过

• 状态数：n×m
• 每列转移：三次线性遍历（入口、向下、向上），每列 O (n)
• 总复杂度：O (n×m)
• 对于 n,m≤1000，一百万次运算，1 秒完全没问题。

总结一下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const ll INF = 1e18; // 负权足够小的初始值

int n, m;
ll a[N][N];
ll dp[N][N]; // dp[i][j]：走到(i,j)时能拿到的最大和，包含a[i][j]

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

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

// 初始化全为负无穷，处理负数权值
for (int i = 0; i <= n + 1; i++)
    for (int j = 0; j <= m + 1; j++)
        dp[i][j] = -INF;

// 起点初始化
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++) {
    vector<ll> left(n+2), down(n+2), up(n+2);

    // 1. 先算从左边走过来的初始值（进入当前列的入口）
    for (int i = 1; i <= n; i++) {
        left[i] = dp[i][j-1] + a[i][j];
    }

    // 2. 从上到下扫：计算「从入口进来后向下走到i」的最优值
    down[1] = left[1];
    for (int i = 2; i <= n; i++) {
        down[i] = max(left[i], down[i-1] + a[i][j]);
    }

    // 3. 从下到上扫：计算「从入口进来后向上走到i」的最优值
    up[n] = left[n];
    for (int i = n-1; i >= 1; i--) {
        up[i] = max(left[i], up[i+1] + a[i][j]);
    }

    // 4. 两种情况取最大值，得到当前列的最终dp值
    for (int i = 1; i <= n; i++) {
        dp[i][j] = max(down[i], up[i]);
    }
}

cout << dp[n][m] << endl;
return 0;

}