一、题目描述 简要描述题目：例如，在一个n×n的方格图中，每个格子包含一个正整数。需要选择两条从左上角到右下角的路径，路径可重复经过格子，但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。
二、解题思路与算法分析
- 问题分析 1.问题核心是求解两条不交叉路径的最优组合，属于路径规划与组合优化问题。 2.直接暴力枚举路径组合的时间复杂度极高（O(2^n×n)），需采用动态规划降低复杂度。 3.关键点：如何定义状态以表示两条路径的当前位置，并确保状态转移时不交叉。
- 动态规划设计
（1）状态定义使用四维数组f[k][i][j]表示： k：两条路径共同走过的步数（即第k步）； i：第一条路径当前所在的行坐标； j：第二条路径当前所在的列坐标。状态值f[k][i][j]为两条路径分别走到(i,j)和某个位置时的最大数字和。
（2）边界条件 初始状态：f[0][1][1] = g[1][1]（两条路径均从起点(1,1)出发，数字和为起点格子值）。 其他状态初始化为负无穷（-0x3f），避免非法状态影响结果。
（3）状态转移方程分情况讨论： 当i == j时，两条路径在同一位置（重复点），只能同时向下或向右移动： （注：g[i][k+2-i]表示当前重复点的数字，因为两条路径同时移动一步。） 当i!= j时，两条路径独立移动，可分别向下或向右： （注：g[i][k+2-i]和g[j][k+2-j]分别表示两条路径当前位置的数字。） （4）最终答案：f[2*n-2][n][n]（两条路径均到达右下角时的最大和）。
- 优化技巧 空间优化：由于状态转移仅依赖前一步的四个状态，可使用滚动数组进一步降低空间复杂度，但用户代码已通过三维数组实现（f[k][i][j]），有效避免了高维数组的存储问题。 边界处理：通过min(n, k+1)限制循环范围，避免无效计算。
三、完整代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 15;
int g[N][N], f[N*2][N][N];
int main() {
int n, x, y, v;
cin >> n;
while((cin >> x >> y >> v) && (x || y || v)) {
g[x][y] = v;
}
memset(f, -0x3f, sizeof f);
f[0][1][1] = g[1][1];
for(int k = 1; k <= 2*n-2; ++k) {
for(int i = 1; i <= min(n, k+1); ++i) {
for(int j = 1; j <= min(n, k+1); ++j) {
int &val = f[k][i][j];
val = max({
f[k-1][i][j],
f[k-1][i-1][j],
f[k-1][i][j-1],
f[k-1][i-1][j-1]
});
if(i == j) val += g[i][k+2-i];
else val += g[i][k+2-i] + g[j][k+2-j];
}
}
}
cout << f[2*n-2][n][n] << endl;
return 0;
}
