这是一个经典的**动态规划（DP）**问题，类似于“数字三角形”或“走方格”，但增加了一个复杂的移动规则：可以向上、向下、向右走，且不能走回头路（不重复经过）。
核心难点
普通的走方格问题通常只能“向右”或“向下”，这样状态转移是单向的，没有后效性。但本题可以“向上”和“向下”走，这意味着在第 jjj 列，我们可以从第 j−1j-1j−1 列跨过来，然后在第 jjj 列内部上下移动。
关键性质
由于不能重复经过方格，且列的方向只能向右（不能向左），我们可以得出一个重要结论：在每一列内部，路径必须是单调的（要么一直向下，要么一直向上，或者不垂直移动）。
* 如果路径在第 jjj 列先向下再向上（例如从 (k,j)(k, j)(k,j) 到 (i,j)(i, j)(i,j) 其中 k<ik < ik<i，然后又回到 (p,j)(p, j)(p,j) 其中 p<ip < ip<i），那么中间的方格就会被重复经过，这是不允许的。
* 因此，到达 (i,j)(i, j)(i,j) 的路径只有三种可能来源：
1. 直接从左边过来：从 (i,j−1)(i, j-1)(i,j−1) 走到 (i,j)(i, j)(i,j)。
2. 从上面下来：从 (k,j−1)(k, j-1)(k,j−1) (k<ik < ik<i) 走到 (k,j)(k, j)(k,j)，然后一路向下走到 (i,j)(i, j)(i,j)。
3. 从下面上来：从 (k,j−1)(k, j-1)(k,j−1) (k>ik > ik>i) 走到 (k,j)(k, j)(k,j)，然后一路向上走到 (i,j)(i, j)(i,j)。
2. 动态规划设计
状态定义
设 dp[i][j]dp[i][j]dp[i][j] 表示从起点 (1,1)(1, 1)(1,1) 走到 (i,j)(i, j)(i,j) 所能获得的最大整数之和。
状态转移
我们需要按列递推（jjj 从 1 到 mmm）。对于第 jjj 列的每个位置 (i,j)(i, j)(i,j)，我们需要计算两个辅助值：
* down[i]down[i]down[i]：表示到达 (i,j)(i, j)(i,j) 且最后一段是在第 jjj 列向下走（或刚从左边过来）的最大值。
* up[i]up[i]up[i]：表示到达 (i,j)(i, j)(i,j) 且最后一段是在第 jjj 列向上走（或刚从左边过来）的最大值。
转移方程：
1. 计算 downdowndown 数组（从上往下扫）：
* 对于第 1 行：只能从左边过来。
down[1]=dp[1][j−1]+a[1][j]down[1] = dp[1][j-1] + a[1][j] down[1]=dp[1][j−1]+a[1][j]
* 对于第 iii 行 (i>1i > 1i>1)：可以从左边直接过来，或者从上面 (i−1,j)(i-1, j)(i−1,j) 走下来。
down[i]=max(dp[i][j−1],down[i−1])+a[i][j]down[i] = \max(dp[i][j-1], down[i-1]) + a[i][j] down[i]=max(dp[i][j−1],down[i−1])+a[i][j]
解释：max(dp[i][j−1],down[i−1])\max(dp[i][j-1], down[i-1])max(dp[i][j−1],down[i−1]) 代表了到达 (i,j)(i, j)(i,j) 上方的最优路径（无论是横向切入还是纵向延续），加上当前格子的值。
2. 计算 upupup 数组（从下往上扫）：
* 对于第 nnn 行：只能从左边过来。
up[n]=dp[n][j−1]+a[n][j]up[n] = dp[n][j-1] + a[n][j] up[n]=dp[n][j−1]+a[n][j]
* 对于第 iii 行 (i<ni < ni<n)：可以从左边直接过来，或者从下面 (i+1,j)(i+1, j)(i+1,j) 走上来。
up[i]=max(dp[i][j−1],up[i+1])+a[i][j]up[i] = \max(dp[i][j-1], up[i+1]) + a[i][j] up[i]=max(dp[i][j−1],up[i+1])+a[i][j]
3. 合并结果：
dp[i][j]=max(down[i],up[i])dp[i][j] = \max(down[i], up[i]) dp[i][j]=max(down[i],up[i])
边界条件与初始化
* 起点：dp[1][1]=a[1][1]dp[1][1] = a[1][1]dp[1][1]=a[1][1]。
* 第一列：只能从上往下走（因为起点在左上角）。
dp[i][1]=dp[i−1][1]+a[i][1]dp[i][1] = dp[i-1][1] + a[i][1] dp[i][1]=dp[i−1][1]+a[i][1]
* 初始值：dpdpdp 数组初始化为负无穷（因为题目中有权值为负的情况）。
3. 代码实现 (C++)
4. 复杂度分析
* 时间复杂度：O(N×M)O(N \times M)O(N×M)。我们遍历了每一列，每列内部进行了两次线性扫描（向下和向上），总操作次数与格子总数成正比。对于 N,M≤1000N, M \le 1000N,M≤1000，运算量约为 10610^6106，完全可以在 1 秒内完成。
* 空间复杂度：O(N×M)O(N \times M)O(N×M)。存储矩阵和 DP 数组需要约 106×810^6 \times 8106×8 字节 ≈8\approx 8≈8 MB，远低于 128MB 的限制。
5. 样例 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。
这与题目样例输出一致。
> 另一个思路供参考:
