题目传送门：
P1006 [NOIP2008 提高组] 传纸条 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言：
本题来源于2008年NOIp 提高组竞赛题目：传纸条，本题涉及到动态DP、图论里的费用流知识点，学过图论的都应该对这道题熟能生巧，可以说非常的简单，但是对于刚学图论的初学者来说也是一个挑战，本题较难将详细了解。（我觉得太简单了！）
# 解题思路：
1、状态设计：
由于我们需要考虑两条路径，直接设计状态比较复杂。我们可以使用四维动态规划数组
dp[x1][y1][x2][y2] 来表示：
dp[x1][y1][x2][y2] 表示：
-
一条路径从
(1,1)到达(x1, y1)； -
另一条路径从
(m,n)到达(x2, y2)； -
在这两条路径上，经过的同学的好心程度之和的最大值。
2、状态初始化：
起点（1，1）与终点（m,n）是固定的，因此： 因为这两点的好心程度必须计算。
3、状态转移：
对于任意状态 dp[x1][y1][x2][y2],我们要考虑一下几种转移方式：
1.1、两条路径分别乡下或向右移动：
-
(x1, y1)向下移动到(x1+1, y1)，(x2, y2)向下移动到(x2+1, y2)。 -
(x1, y1)向右移动到(x1, y1+1)，(x2, y2)向右移动到(x2, y2+1)。
1.2、一条路径向下，另一条路径向右：
-
(x1, y1)向下移动到(x1+1, y1)，(x2, y2)向右移动到(x2, y2+1)。 -
(x1, y1)向右移动到(x1, y1+1)，(x2, y2)向下移动到(x2+1, y2)。
在每种转移中，我们需要加上当前点的好心程度。如果两条路径在某一点重合（即 (x1, y1) == (x2, y2)），则该点的好心程度只能计算一次。
4、边界条件：
如果两条路径在某一点重合（除起点和重点），则该状态无效
即 dp[x1][y1][x2][y2] = -1）。
如果两条路径分别到达终点（m,n）和起点（1，1），则dp[m][n][1][1]
即为最终答案。
5、动态规划顺序：
由于状态转移是从较小的坐标向较大的坐标进行的，因此我们需要按照坐标从小到大的顺序填充 dp 数组。具体来说：
-
外层循环：
x1和y1，表示从(1,1)到(m,n)的路径。 -
内层循环：
x2和y2，表示从(m,n)到(1,1)的路径。
##优化思路：
优化1、二维动态规划：
我们可以将两条路径的动态规划合并为一个二维状态：
1.1、定义 dp[i][j][k][l] 表示两条路径分别到达（i,j）和（k,l）的最大好心程度和。
1.2、由于两条路径不能相重叠，因此 i+j=k+1 （即两条路径的总步数相同）。
1.3、因此，我们可以将状态压缩为 dp[i][j][k] ，期中 l=i+j-k 。
优化2、空间优化：
在实际实现中，可以使用滚动数组的方式进一步优化空间复杂度，将四维数组压缩为三维或二维数组。
###代码：
#include <bits/stdc++.h>
using namespace std;
int m, n;
int main() {
cin >> m >> n;
vector<vector<int>> r(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> r[i][j];
}
}
vector<vector<vector<vector<int>>>> dp(m + 1, vector<vector<vector<int>>>(n + 1,
vector<vector<int>>(m + 1, vector<int>(n + 1, -1))));
dp[1][1][1][1] = r[1][1];
for (int x1 = 1; x1 <= m; ++x1) {
for (int y1 = 1; y1 <= n; ++y1) {
for (int x2 = 1; x2 <= m; ++x2) {
for (int y2 = 1; y2 <= n; ++y2) {
if (dp[x1][y1][x2][y2] == -1) continue;
if (x1 < m && x2 < m) {
dp[x1 + 1][y1][x2 + 1][y2] = max(dp[x1 + 1][y1][x2 + 1][y2],
dp[x1][y1][x2][y2] + r[x1 + 1][y1] + (x1 + 1 != x2 + 1 || y1 != y2 ? r[x2 + 1][y2] : 0));
}
if (x1 < m && y2 < n) {
dp[x1 + 1][y1][x2][y2 + 1] = max(dp[x1 + 1][y1][x2][y2 + 1],
dp[x1][y1][x2][y2] + r[x1 + 1][y1] + (x1 + 1 != x2 || y1 != y2 + 1 ? r[x2][y2 + 1] : 0));
}
if (y1 < n && x2 < m) {
dp[x1][y1 + 1][x2 + 1][y2] = max(dp[x1][y1 + 1][x2 + 1][y2],
dp[x1][y1][x2][y2] + r[x1][y1 + 1] + (x1 != x2 + 1 || y1 + 1 != y2 ? r[x2 + 1][y2] : 0));
}
if (y1 < n && y2 < n) {
dp[x1][y1 + 1][x2][y2 + 1] = max(dp[x1][y1 + 1][x2][y2 + 1],
dp[x1][y1][x2][y2] + r[x1][y1 + 1] + (x1 != x2 || y1 + 1 != y2 + 1 ? r[x2][y2 + 1] : 0));
}
}
}
}
}
cout << dp[m][n][m][n] << endl;
return 0;
}
