一、问题描述
设有 N×NN×N 的方格图 (N≤9)(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 00。如下图所示（见样例）:
图1
某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
二、问题分析
图2
这个问题是一道非常经典的动态规划问题。首先咱们介绍一下动态规划算法，如图二。法如其名，这个算法的过程是动态的，不同于暴力算法，舍弃了一些冗余的计算，只计算有可能成为题解的结果，最后得出最优解。能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构：具有最优子结构的问题也可能是适合用贪心的方法求解。等会会介绍第一个错误案例的贪心讲解。另外注意要确保我们考察了最优解中用到的所有子问题。
证明问题最优解的第一个组成部分是做出一个选择；
对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。
无后效性：已经求解的子问题，不会再受到后续决策的影响。
子问题重叠：
如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。
那么现在我们来正式分析一下这个问题，首先是最优子结构，要想得到最后一步的最大结果，我们就得得到前一步的最大结果，这一点和01背包不约而同。所以可以得到二维的状态转移方程是这样的：
f[i][j]=max(f[i−1][j],f[i][j−1])+val[i][j]
然后是无后效性，f[i][j] 只依赖于f[i−1][j]和f[i][j−1]，即当前位置的最优解只与前两个可能的转移状态相关，而与路径到达这些状态的具体方式无关。这意味着，只要我们记录当前状态 f[i][j]和其来源（即 pre[i][j]的值），就足以确定路径的最优解。
无后效性保证了在清零第一条路径后，第二条路径的动态规划依然是无后效性的。对于第二条路径的状态 f′[i][j]，它同样只依赖于f′[i−1][j] 和 f′[i][j−1]，清零操作并不会影响状态转移的无后效性。
最后是子问题重叠。子问题重叠是动态规划的另一个重要特性，指同一个子问题会在递归或迭代过程中被多次计算。
在路径规划的过程中，矩阵中的每一个点(i,j)需要计算其最优值 f[i][j]，但在递归或迭代中，可能会多次到达这个点。例如，如果路径从 (i−1,j)和(i,j−1)同时可以转移到 (i,j)(i, j)(i,j)，则 f[i][j]的值会被重复计算。通过用数组 f[i][j]存储中间状态（即子问题的解），避免了重复计算，从而降低了时间复杂度。
综上所述，最后采用动态规划的算法去解决这一道题目是比较合理的。
三、算法设计
首先是二维动态规划，这个算法是在我学习尚未充分的情况下完成的。并不是最完好的解法，下面讲解一下我的思路。
二维动态规划：
首先是初始化数据，利用while判断终止条件。然后是第一次的动态规划，找到第一次路径的最大值。状态转移方程是这样的：f[i][j]=max(f[i-1][j],f[i][j-1])+val[i][j]。
利用if判断f[i-1][j]和f[i][j-1]的大小关系是从上面还是左边来的。再进行一次清零操作，返回操作，从末尾到开始，把第一条路径走过的值重新变成0。然后再一次进行二维的动态规划。
把两次动态规划的结果相加即可得到二维动态规划的最大值。
图3——两次动态规划的结果
图4——另一种更优的解法
但是这样的并非最佳，如图3图4，只是贪心的“鼠目寸光”，这样的处理只是最优+最优，可以得到一个相较最优，而实际的处理起来要通过二维动态规划得到真正的答案十分麻烦，是需要两个同时达到最优的。所以还得继续优化。此时在学习过更高维度的动态规划算法后，我决定使用四维动态规划作为真正的解答。
四维动态规划：
四维不同于二维，是把两条路线都综合在一起考虑了，即是枚举了两种路线分别经过一个点的状态，并且放在一起考虑。
1.状态解释
dp[i][j][k][l]表示从(1,1）开始，两个人分别到达 (i,j)和(k,l)时，两条路径的最大点权值和。
a[i][j]表示第一个人经过的点的权值。
a[k][l]表示第二个人经过的点的权值。
两个人的移动路径是独立的，但要满足：两人都只能向右或向下，两人不能同时走过同一个点。
2. 状态转移方程的推理
从当前状态 (i,j,k,l)可以通过以下几种方式转移：
第一个人向下，第二个人向下：dp[i−1][j][k−1][l]
第一个人向下，第二个人向右：dp[i−1][j][k][l−1]
第一个人向右，第二个人向下：dp[i][j−1][k−1][l]
第一个人向右，第二个人向右：dp[i][j−1][k][l−1]
所以可以得到状态转移方程：
dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];
特殊情况：
如果(i,j)和(k,l)是同一个点（即ik且jl），则要避免重复计入点权值，所以：
dp[i][j][k][l]−=a[i][j]
3. 边界条件
初始化dp[1][1][1][1]=a[1][1]，即两个人都在起点时的最大权值为起点的权值。
数组 dp[i][j][k][l]中的所有其他状态初始化为 0。
然而正如下面算法分析所言一样，四维的动态规划时间复杂度太高O（n**4），所以应该使用三维动态规划来优化。
三维动态规划：
1.状态定义：f[k][i][j]表示两个人分别走到第 k步时，第一人位于(k−i,i)，第二人位于 (k−j,j)的最大路径权值和。
k表示总步数（第一人和第二人移动的步数相同）。
i和j分别是第一人和第二人的纵坐标
k−i和k−j分别是第一人和第二人的横坐标
2. 状态转移方程的推理
在第 k步时，第一人和第二人可以分别从第 k−1步的某个状态转移而来。每个人有两种可能的移动方向（向右或向下），因此共有4种转移方式：
第一人向下，第二人向下：f[k−1][i−1][j−1]
第一人向下，第二人向右：f[k−1][i−1][j]
第一人向右，第二人向下：f[k−1][i][j−1]
第一人向右，第二人向右：f[k−1][i][j]
根据这四种可能性，状态转移方程为：
f[k][i][j]=max(f[k−1][i−1][j−1],f[k−1][i][j−1],f[k−1][i−1][j],f[k−1][i][j])+val[k−i][i]+val[k−j][j]
特殊情况：
如果两个人到达同一个格子，即 (k−i,i)==(k−j,j)，需要避免重复计入权值，所以：
f[k][i][j]−=val[k−i][i]
3. 边界条件
在第 k=2步时，两人只能从起点(1,1) 出发，因此初始值为0，且动态规划表 f[k][i][j]已经考虑了第一个有效的步数。
f[k][i][j]的初始值默认为0，因为没有经过合法路径的点权值和为 0。
4. 最终答案
两人分别从 (1,1)(1,1)(1,1) 出发到达 (n,n)(n,n)(n,n)，总步数为 k=2n，因此最终答案为：
f[2n][n][n]
四、算法分析
二维动态规划的算法思想参杂了一些贪心算法，即第一次找出最大值，再第二次找出最大值，这样看似可以得出最优解，但是实际却不如人意。因为一次操作只能向下或者向右，那么同一行同一列在经历一次操作过后就失去了可取性。有可能第一次可以取到的值可以留给第二次顺路去取，这样第一次就可以去取一个相对较小一些的值。时间复杂性上两次二维动态规划是O（n²），一次清零操作是O（n），综合起来是O（n²）。
相比较二维的动态规划，四维的动态规划实现了两条路径同时达到最优，结果上来说是正确的，但是还是不够完美，毕竟是四维的动态规划，四次循环的时间复杂度是O（n4）对于空间时间占比过于庞大，所以能否有一个优化方案呢？
答案是有的，就在四与二之中：三维动态规划优化。
三维的复杂度影响只有两个，一个是存储值的val，复杂度是O（n²），而三维动态规划的复杂度也是三次for循环的复杂度，结果是O（n3）
五、总结讨论
从二维到四维再到三维，让我深刻地认识到了动态规划算法的核心思想：大事化小，小时化了。
第一次是使用二维动态规划 + 贪心，先找到第一条路径的最大值，并将其路径上的点清零，然后再用第二次二维动态规划计算第二条路径的最大值。
时间复杂度上来说最低，但是贪心策略导致结果不一定最优，因为第一条路径可能优先选择了一些点，使得第二条路径的潜在价值大大降低。每次路径的计算是独立的，没有考虑两条路径的全局最优。
之前以为两次二维动态规划就是最优解了，直到学习了四维动态规划。
第二次是四维动态规划。用四维状态同时计算两条路径，并避免两人经过同一个点，这是实现四维里面卡了很久的点，虽然整体的代码不多，但是特殊情况这一边的思维难度很高。这样保证了两条路径的全局最优解，因为状态转移时同时考虑了两人的移动。不仅解决了二维动态规划的贪心遗留下的问题，还有着更清晰的算法思路。但是时间复杂度上来说太过复杂，无法解决大规模的问题。
于是三维动态规划应运而生。
基于k=x1+y1=x2+y2的性质，将四维状态压缩为三维状态dp[k][i][j]。成功将时间复杂度降低为O(n^3)，相较于四维动态规划大幅优化。三维这一边的难点也是思维上的，比较难以想到，并且三维的边界问题也比较复杂。
当然了，这道题也不止动态规划的一个解决方案，也可以用深度优先搜索+记忆化搜索来解决问题。 核心思想是递归模拟所有的运动情况，并且用记忆化搜索避免重复运算，但是这种情况出现的特殊情况比较多，处理起来很繁琐，时间复杂度也是O（n^4）.作为路径搜索类的问题，这道题当然也可以用A*算法解决。
六、附录：完整程序代码
七、附录：运行结果截图
二维动态规划
点击查看代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=10;
int ans=0;
int f[N][N];
int pre[N][N];//记录前一个位置
int val[N][N];
int main(){
int n;cin>>n;
int a,b,c;
while(cin>>a>>b>>c){
if(a==0&&b==0&&c==0){
break;
}
val[a][b]=c;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
f[i][j]=max(f[i-1][j],f[i][j-1])+val[i][j];
if(f[i-1][j]>=f[i][j-1]){
pre[i][j]=1;//1从上一行来
}
else{
pre[i][j]=2;//2从左边来
}
}
}
for(int i=1;i<=n;++i) pre[1][i]=2;
for(int i=1;i<=n;++i) pre[i][1]=1;
ans+=f[n][n];
memset(f,0,sizeof f);
int line=n;
int rank=n;
val[rank][line]=0;
while(rank>1||line>1){
if(pre[rank][line]==1){
rank-=1;
}
else{
line-=1;
}
val[rank][line]=0;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
f[i][j]=max(f[i-1][j],f[i][j-1])+val[i][j];
}
}
ans+=f[n][n];
cout<<ans<<endl;
return 0;
}
四维动态规划
点击查看代码
#include<cstdio>
#include<iostream>
using namespace std;
const int N=11;
int dp[N][N][N][N];
int a[N][N];
int n,x,y,z;
int main()
{
scanf("%d",&n);
for(;;)
{
scanf("%d%d%d",&x,&y,&z);
if(x==y&&y==z&&z==0)
{
break;
}
else
{
a[x][y]=z;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
for(int l=1;l<=n;l++)
{
dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];
if(i==k&&l==j)dp[i][j][k][l]-=a[i][j];
}
}
}
}
printf("%d",dp[n][n][n][n]);
return 0;
}
三维动态规划
点击查看代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
int ans=0;
int f[N][N][N];
int val[N][N];
int main(){
int n;cin>>n;
int a,b,c;
while(cin>>a>>b>>c){
if(a==0&&b==0&&c==0){
break;
}
val[a][b]=c;
}
for(int k=2;k<=n*2;++k){//从2开始，不能从3，因为要考虑（1，1）的情况
for(int i=1;i<=min(k-1,n);++i){//k-1 是因为要考虑横坐标至少有1
for(int j=1;j<=min(k-1,n);++j){
f[k][i][j]=max(max(f[k-1][i-1][j-1],f[k-1][i][j-1]),
max(f[k-1][i-1][j],f[k-1][i][j]))+val[k-j][j]+val[k-i][i];
if(i==j) f[k][i][j]-=val[k-i][i];
//重复就减掉
}
}
}
cout<<f[n*2][n][n]<<endl;
return 0;
}
图5
图5处三个动态规划的结果一致。
图6——二维动态规划+贪心
图7——四维或三维动态规划的正确结果