动态规划DP 数字三角型模型 方格取数（题目详解+C++代码实现）

方格取数

原题链接

AcWing 1027. 方格取数

题目描述

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。
如下图所示：

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式
第一行为一个整数N，表示 N×N 的方格图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。
行和列编号从 1开始。
一行“0 0 0”表示结束。

输出格式
输出一个整数，表示两条路径上取得的最大的和。

数据范围
N≤10

输入样例：

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例：

67

题目分析

与 摘花生 类似，不同点在于该题方格取数要找出两条路径，使其和最大。
回忆 摘花生 动态规划数字三角形模型思考。

摘花生（只走一次）：
$f[i,j]$ 表示左右从 $(1,1)$ 走到 $(i,j)$ 的路径的最大值
$f[i,j]=max(f[i-1,j]+w[i][j],f[i,j-1]+w[i,j])$

方格取数（走两次）：
利用摘花生的思想，同时维护两条路径，用$f[i1,j1,i2,j2]$ 表示所有从 $(1,1),(1,1)$ 分别走到 $(i1,j1),(i2,j2)$ 的路径的最大值。

同时，每走一格，要么是$i+1$，要么是$j+1$，并且由于是同时出发的两条路径，则一定满足**$i1+j1=i2+j2$** 。据此，我们可以化简状态$f[i1,j1,i2,j2]$，令 $k=i1+j1=i2+j2$ ，表示两条路径走到的格子的横纵坐标之和。
$f[k,i1,i2]$ 表示所有从 $(1,1),(1,1)$ 分别走到 $(i1,k-i1),(i2,k-i2)$ 的路径的最大值。

但需要注意的是，当两条路径走到同一个格子时，一个方格中的数字只能被取一次，则如何处理“同一个格子不能被重复选择”？
我们知道，只有在 $i1+j1=i2+j2$ 时，两条路径的格子才可能重合。即为在同一个 $k$ 下，同时满足$i1=i2$ 时，两条路径的格子重合。此时，该方格内的数字只被加一次。

状态计算

用 $t$ 表示下一步需要取的数字之和，
若两条路径不重合，则 $t=w[i1][j1]+w[i2][j2]$，
若两条路径重合，则 $t=w[i1][j1]$（只用加一次）。

状态的转移计算示意图如下：
路径从左至右：则由 $i-1$至 $i$，由$k-1$至$k$。
路径从上至下：则 $i$ 不变，由$k-1$至$k$。

第一条路径：从左至右；第二条路径：从左至右：
$f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2-1]+t)$
第一条路径：从左至右；第二条路径：从上至下：
$f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2]+t)$
第一条路径：从上至下；第二条路径：从上至下：
$f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2]+t)$
第一条路径：从上至下；第二条路径：从左至右：
$f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2-1]+t)$

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=15;
int n;
int w[N][N];  //权重
int f[N*2][N][N];  //状态计算
int main(){
    scanf("%d",&n);
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b]=c;
    for(int k=2;k<=n+n;k++){
        for(int i1=1;i1<=n;i1++){
            for(int i2=1;i2<=n;i2++){
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){  //j符合条件
                    int t=w[i1][j1];  //第一条路径
                    if(i1!=i2) t+=w[i2][j2];  //如果第二条路径与第一条路径重合，则权重w[i][j]不能重复增加
                    int &x=f[k][i1][i2];  //使用&简化代码
                    x=max(x,f[k-1][i1-1][i2-1]+t);  //第一条路径：来自上方；第二条路径：来自上方
                    x=max(x,f[k-1][i1-1][i2]+t);  //第一条路径：来自上方；第二条路径：来自左方
                    x=max(x,f[k-1][i1][i2]+t);  //第一条路径：来自左方；第二条路径：来自左方
                    x=max(x,f[k-1][i1][i2-1]+t);  //第一条路径：来自左方；第二条路径：来自上方
                }
            }
        }
    }
    printf("%d\n",f[n+n][n][n]);
    return 0;
}