数字三角形模型

数字三角形模型DP是线性DP的一类，有非常多的变式，不过本质是从顶部出发，向右或下走，即满足数字三角形的所有条件。

例1 Acwing898.数字三角形

标程：

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int f[N][N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= i; j ++ ){
            cin >> f[i][j];
        }
    }

    for (int i = n; i >= 1; i -- ){
        for (int j = i; j >= 1; j -- ){
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];
        } // 从底向上出发，不考虑边界问题
    }

    cout << f[1][1] << endl;

    return 0;

}

例2 Acwing1015.摘花生

经典的数字三角形模型，甚至不需要考虑边界问题。

标程

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N]; //表示走到i，j时的最大数量

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        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 i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]; // 状态转移方程，表示从左或上走来

        printf("%d\n", f[n][m]);
    }

    return 0;
}

例3 Acwing1018.最低通行费

和摘花生一题类似

标程：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;

int q[maxn][maxn];
int f[maxn][maxn];
int n;

int main()
{
    memset(f, 0x3f, sizeof f); // 初始化为inf，因为我们要取得是min
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ) cin >> q[i][j];
    }
    
    f[1][1] = q[1][1];
    
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            f[i][j] = min({f[i][j], f[i - 1][j] + q[i][j], f[i][j - 1] + q[i][j]});
        }
    }
    cout << f[n][n] << endl;
}

例4 Acwing1027.方格取数

相对麻烦的数字三角形模型，因为需要找两条路径。

一种可行的办法是先走一条路，存下走过的路径，清零后再找一次第二条路。

还有一种方法，我们可以同时走两条路，多开几个状态来表示两条路。这样的话，最直观的方法是用四个状态维护i1,i2,j1,j2，进行状态转移。

不过我们可以得到 i1 + j1 = i2 + j2 的方程，即可设i1 + j1 = k，那么用三维即可满足所有的状态。

j1 = k - i1, j2 = k - i2;

标程：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 15;
int q[maxn][maxn];
int f[maxn * 2][maxn][maxn];
int a, b, c;
int n;

int main()
{
    cin >> n;
    while (cin >> a >> b >> c, a || b || c) q[a][b] = c;
    
    
    for (int k = 2; k <= 2 * 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 t = q[i1][j1];
                    if (i1 != i2) t += q[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][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2] + t);//四种状态转移方程
                }
            }
        }
    }
    cout << f[2 * n][n][n] << endl;
}