[数据结构与算法]dp专题之数字三角模型

简单的线性dp
这种题目我们只需要找到当前状态的是由那些状态得来的即可。
比较十分经典的摘花生问题（问题来源：acwing） 题目戳我

对于这个问题，我们简单来分析一下，当前和这个格子的总花生数的来源是哪呢？
由于题目说了，他只能往下或者往右走，也就是他的来源就是左边或者上面，但是请不要忘记，当前的位置的花生数一定要加上当前这个位置的花生数，他继承来源于左方或者上方的花生数，同时拿走他当前位置的花生数， 就组成了从起点开始到当前位置最大的花生数。

核心状态转移方程为：f[i][j] = max(f[i-1][j],f[i][j-1]) + a[i][j]

下面是完整的代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int T;
int a[110][110];
int f[110][110];
int main()
{
    cin >>T;
    while(T--){
        memset(a,0,sizeof a);
        memset(f,0,sizeof f);
        int r,c;
        cin >>r>>c;
        for(int i=1; i<=r; i++){
            for(int j=1; j<=c; j++){
                cin >>a[i][j];
            }
        }
        
        for(int i=1; i<=r; i++){
            for(int j=1; j<=c; j++){
                f[i][j] = max(f[i-1][j],f[i][j-1]) + a[i][j];
            }
        }
        cout<<f[r][c]<<endl;
    }
    return 0;
}

是不是有了了解了，感觉非常的神奇和easy
下面我们来增加一点点边界问题
最低通行费用(题目来源：acwing)
题目戳我

扎眼一看，感觉和摘花生没啥区别，直接copy一份代码：
调试一下，发现通过不了样例，因为这个问题是最小值，那么他可能会一直走边界0的情况，这里我们单独处理一下边界情况就可以，然后状态转移的时候忽略一下即可
状态转移方程还是没什么变化的：f[i][j] = min(f[i-1][j],f[i][j-1]) + a[i][j]。

这个单独处理的代码为：

for(int i=1; i<=n; i++){
        f[i][1] = f[i-1][1] + a[i][1];
        f[1][i] = f[1][i-1] + a[1][i];
    }

但是这里我们也可以不进行处理，我们单独进行一些初始化即可，我们将f数组初始化为0x3f那么也可以避免这种情况，具体的代码不妨由你参考摘花生来完成！
完整代码为：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=110;
int n;
int a[maxn][maxn];
int f[maxn][maxn];
int main()
{
    cin >>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >>a[i][j];
        }
    }
    
    for(int i=1; i<=n; i++){
        f[i][1] = f[i-1][1] + a[i][1];
        f[1][i] = f[1][i-1] + a[1][i];
    }
    
    for(int i=2; i<=n; i++){
        for(int j=2; j<=n; j++){
            f[i][j] = min(f[i-1][j],f[i][j-1]) + a[i][j];
        }
    }
    
    
    cout<<f[n][n];
    return 0;
}

这样我们基本就了解了这种问题，下面我们来深入一下。
放格取数(题目来源：acwing)
题目戳我
这个题目我们可以看成是摘花生的进阶版，我们要选两条路，一条最大，一条次大，且两条路不能取重复的参数点，这个怎么办呢？
我们对摘花生的处理是代表到i行j列的最大值，那么我们对他就是要两条嘛。
也就是四个维度，我们可以进行一下优化，通过一个共同的属性，那就是通过步数来联系起这两个维度，和参数，我们就只需要步数，这两条线的横坐标就可以表示出这个状态了。
例如：f[k][i][j]表示从七点走了k步，且两条线的当前位置分别为i,k-1和j,k-j等等。
那么思路就清晰了，我们只需要维护一下这三个参数即可，但千万记的特别的情况，两条线不能选取同样的参数点，也就是我们需要去判断是否重合，因为有k的制约，所以，只要判断他的横坐标或者纵坐标任意一个就行。
因为有两条线，每条线都有右和下两种操作，那么两条线共有四种操作。
状态转移方程：
*说明：*这里面的p(我们将他初始化为第一条线的当前位置参数)就是当前位置的参数，用之前我们要判断一下 i==j 如果是false 那么t要加上第二条线的当前位置参数，否则就不予理会
f[k][i][j] = max(f[k][i][j],f[k-1][i][j]+p) 这代表两条线的操作都是 “右右”

f[k][i][j] = max(f[k][i][j],f[k-1][i][j-1] 这代表两个操作分别为“右下”

f[k][i][j] = max(f[k][i][j],f[k-1][i-1][j] 这代表两个操作分别为 “下右”

f[k][i][j] = max(f[k][i][j],f[k-1][i-1][j-1] 这两个操作分别为 “下下”

核心代码：

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){
                    int p = q[i1][j1];
                    if(i1!=i2) p+=q[i2][j2];
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2-1]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2-1]+p);
                }
            }
        }
    }

我们还有特别处理一下这个输入问题，可以这样
while(cin >>a>>b>>c,a||b||C)
也可以这样
while(scanf("%d%d%d",&a,&b,&c)==3)

这两个操作都是一样的含义：读入三个数，第一个意思为这三个数进行 或 运算，也就是不能全为0，第二个，则代表三个数都正常输入了，刚好0不在这个范围内，所以他的意思就是scanf读入至少一个0，就不满足while了

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=  15;
int n;
int q[maxn][maxn];
int f[2*maxn][maxn][maxn];
int main()
{
    cin >>n;
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)==3) q[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){
                    int p = q[i1][j1];
                    if(i1!=i2) p+=q[i2][j2];
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2-1]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2-1]+p);
                }
            }
        }
    }
    cout<<f[n+n][n][n]<<endl;
    return 0;
}

下面我们再来看看这个题目，他和上一个取数差不多，有了些许的小变化
传纸条(题目来源：acwing)
题目戳我
这个题目整体含义是差不多的，他虽然说要先去再回，但是我们可以直接等价成两条路线去。那么这个问题就和前面的取方格数一样的。

废话不多说
上代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=  55;
int n,m;
int q[maxn][maxn];
int f[2*maxn][maxn][maxn];
int main()
{
    cin >>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >>q[i][j];
        }
    }
    for(int k=2; k<=n+m; k++){
        for(int i1=max(1,k-m); i1<=min(n,k-1); i1++){
            for(int i2=max(1,k-m); i2<=min(n,k-1); i2++){
                    int p = q[i1][k-i1];
                    if(i1!=i2) p+=q[i2][k-i2];
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2-1]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2]+p);
                    f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2-1]+p);
            }
        }
    }
    cout<<f[n+m][n][n]<<endl;
    return 0;
}

这样是能过的，但是要切合题意，我们再来看一下，在对p进行处理的时候，他是一定不能走重复的格子的，而取方格数那个题，他是可以走的，只不过第二个没有值罢了，所以我们再这里最好改一下。

更改的代码：(取代掉i2循环里面的代码)
这里面我们要注意的就是这个if的条件，就是不能取相同的格子，但是这里我们还要对起点和终点特判一下，因为这两个点是一定会重复的。

    int p = q[i1][k - i1];
    if (i1 != i2 || k == 2 || k == n + m)
    {
        t += q[i2][k - i2];
        f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2]+p);
        f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1-1][i2-1]+p);
        f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2]+p);
        f[k][i1][i2] = max(f[k][i1][i2],f[k-1][i1][i2-1]+p);
    }

有问题欢迎大家指正，滴滴我。