动态规划DP 数字三角形模型（模型分析+例题分析+C++代码实现）（数字三角形、摘花生、最低通行费用、方格取数、传纸条）

总体概览

数字三角形

原题链接

AcWing 898.数字三角形

题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数，表示最大的路径数字和。

数据范围
1≤n≤500, −10000≤三角形中的整数≤10000

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

题目分析

动态规划分析-闫式思考法

从集合角度来考虑DP问题，用 f[i,j] （状态表示）来表示所有从 (1,1) 走到 (i,j) 的路线（集合），并记录更新所有路线中所经数字和的最大值（属性）。
i，j的划分如下图所示。

题目分析可知，只能向左下走或向右下走，则对于任一点 (i,j) 来说，上一个点只能来自左上或右上（状态划分）。据此进行状态计算。

状态计算可知，f[i,j] 取为二者的最大值。

初始化问题

对于很多的边界问题，多初始化一些f值（-INF）,避免边界问题。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=510;
const int INF=1e9;  //负无穷
int f[N][N];  //状态值
int a[N][N];  //三角形值
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    //初始化
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            f[i][j]=-INF;
        }
    }
    //起始点(1,1)不由左上、右上得到，而直接初始化为a[1][1]
    f[1][1]=a[1][1];
    //状态计算
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    int res=-INF;
    //结果选取最后一行的最大值
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}

摘花生

原题链接

AcWing 1015. 摘花生

题目描述

Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。

输入格式
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

题目分析

动态规划分析-闫式思考法

从集合角度来考虑DP问题，用 f[i,j] （状态表示）来表示所有从 (1,1) 走到 (i,j) 的路线（集合），并记录更新所有路线中所经花生数量的最大值（属性）。
题目分析可知，只能向东或向南走即向左或向下走，则对于任一点 (i,j) 来说，上一个点只能来自左边或上边（状态划分）。据此进行状态计算。


状态计算可知，f[i,j] 取为二者的最大值。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int w[N][N];  //存储花生数
int f[N][N];  //存储状态下的属性
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int x,y;
        scanf("%d%d",&x,&y);  //行、列数
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++){
                scanf("%d",&w[i][j]);  //各格点花生数
            }
        }
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++){
                //状态计算：最后一步从左面来||最后一步上面来
                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
            }
        }
        printf("%d\n",f[x][y]);  //最终结果为走到终点(x,y)的状态值
    }
    return 0;
}

最低通行费用

原题链接

AcWing 1018. 最低同行费用

题目描述

一个商人穿过一个 N×N的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。每穿越中间 1个小方格，都要花费 1个单位时间。商人必须在 (2N−1)个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

输入格式
第一行是一个整数，表示正方形的宽度 N。后面 N行，每行 N个不大于 100的正整数，为网格上每个小方格的费用。
输出格式
输出一个整数，表示至少需要的费用。

数据范围
1≤N≤100

输入样例：

5
1  4  6  8  10
2  5  7  15 17
6  8  9  18 20
10 11 12 19 21
20 23 25 29 33

输出样例：

109

样例解释
样例中，最小值为 109=1+2+5+7+9+12+19+21+33。

题目分析

“商人必须在 (2N−1)个单位时间穿越出去” 意味着不能走回头路，
因此，该题转化为 “ 摘花生 ”。

不同点在于，该题 “最低通行费” 所求为最小值（min），而 “摘花生” 所求为最大值（max）。

全局变量的初值默认为0，最小值（min）在求解过程中可能涉及到初始化问题，因为0可以是最小值，而边界情况又是不合理的，需要我们多加处理。

数据的初始化处理

第一列 （i，1）：
路径不可能来自第一列的左侧，f[i][0] 初始化为INF。
第一行（1，j）：
路径不可能来自第一行的上侧，f[0][j] 初始化为INF。

同时，在状态计算的过程当中，路径一定过起点（1，1），因此，f[1][1]的状态值不由f[0][1]或者f[1][0]得到，而是直接赋值为 w[1][1]。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
const int INF=2e9;
int n;
int w[N][N];  //费用
int f[N][N];  //状态表示
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&w[i][j]);
        }
    }
    //初始化处理
    for(int i=1;i<=n;i++){
        f[i][0]=INF;  //第一列的左侧
        f[0][i]=INF;  //第一行的上侧
    }
    //状态计算
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1&&j==1) f[1][1]=w[1][1];  //如果是起始点(1,1)，则直接赋值w[1][1]
            else f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];  //否则通过状态计算
        }
    }
    printf("%d",f[n][n]);  //右下角终点(n,n)的f状态值即为最终答案
    return 0;
}

方格取数

原题链接

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;
}

传纸条

原题链接

AcWing 275. 传纸条

题目描述

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。

一次素质拓展活动中，班上同学安排坐成一个 m行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。

幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。

从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。

班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0表示），可以用一个 0∼100的自然数来表示，数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式
第一行有 2个用空格隔开的整数 m和 n，表示学生矩阵有 m行 n列。
接下来的 m行是一个 m×n的矩阵，矩阵中第 i行 j列的整数表示坐在第 i行 j列学生的好心程度，每行的 n个整数之间用空格隔开。

输出格式
输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

数据范围
1≤n,m≤50

输入样例：

3 3
0 3 9
2 8 5
5 7 0

输出样例：

34

题目分析

与 方格取数 类似，只需将从右下角传递小纸条至左上角也理解为从左上角传递至右下角即可。用$f[k,i1,i2]$ 表示状态。
“只会帮他们一次”即为“同一个格子只会被选择一次”。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=55;
int n,m;
int w[N][N];
int f[N*2][N][N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&w[i][j]);
        }
    }
    for(int k=2;k<=n+m;k++){
        for(int i1=max(1,k-m);i1<=min(k-1,n);i1++){
            for(int i2=max(1,k-m);i2<=min(k-1,n);i2++){
                int j1=k-i1,j2=k-i2;
                int t=w[i1][j1];
                if(i1!=i2) t+=w[i2][j2];
                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",f[n+m][n][n]);
    return 0;
}