数字三角形模型

AcWing 1015. 摘花生

理解

属于数字三角形问题中最简单的一种，即给出矩阵然后计算从起始点到最终点（最大/最小）价值
此题是计算最大值，只需把f数组初始化为0，然后根据最后一步是由上面的格子和左边的格子得来的得到状态计算方程，即可得出

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int> (m + 1, 0)), f(n + 1, vector<int> (m + 1, 0));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[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]) + a[i][j];
        }
    }

    cout << f[n][m] << endl;
}

int main() {
    int T;
    cin >> T;
    while (T --) {
        solve();
    }

    return 0;
}

AcWing 1018. 最低通行费

理解

这题和摘花生相同，只是最后要求得是最小值。所以有个细节需要改动：处于最上面一行的数字不能从它的上面得到，处于最左边的数字不能从它的左边得到，我们只需要将它赋为INF即可

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9 + 10;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(n + 1, vector<int> (n + 1, 0)), f(n + 1, vector<int> (n + 1, 0));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n; j ++) {
            if (i == 0 || j == 0) f[i][j] = INF;
        }

    f[0][1] = f[1][0] = 0;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++) 
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + a[i][j];

    cout << f[n][n] << endl;
}

int main() {
    int T = 1;
    //cin >> T;
    while (T --) {
        solve();
    }

    return 0;
}

AcWing 1027. 方格取数

理解

这题是摘花生的升级版，摘花生只需要走一次，这题需要走两次，且每个点的值只能算一次
故而思路改成从(1,1)走到（i1, j1）和（i2, j2），走两条路径。走到了相同的点则只取一次值，否则取两个点值之和

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 15;
int f[N * 2][N][N];


int main() {
    int n;
    cin >> n;
    vector<vector<int> > a(n + 1, vector<int> (n + 1, 0));

    int x, y, g;
    cin >> x >> y >> g;
    while (x || y || g) {
        a[x][y] = g;
        cin >> x >> y >> g;
    }

    for (int k = 2; k <= n + n; k ++) {                                    //k为i + j。逻辑为当且仅当i1 + j1 == i2 + j2时有可能走到相同的点上
        for (int i1 = 1; i1 <= n; i1 ++) {
            for (int i2 = 1; i2 <= n; i2 ++) {
                int j1 = k - i1, j2 = k - i2;
                if (j1 <= n && j1 >= 1 && j2 <= n && j2 >= 1) {
                    int t = a[i1][j1];
                    if (i1 != i2) t += a[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 - 1] + t);
                    x = max(x, f[k - 1][i1][i2] + t);                     //若该点是由都向右得来
                }
            }
        }
    }

    cout << f[n + n][n][n] << endl;

    return 0;
}

AcWing 275. 传纸条

理解

和方格取数是同样的题

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 55;
int f[N * 2][N][N];


int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > a(n + 1, vector<int> (m + 1, 0));

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

    for (int k = 2; k <= n + m; k ++) {
        for (int i1 = 1; i1 <= n; i1 ++) {
            for (int i2 = 1; i2 <= n; i2 ++) {
                int j1 = k - i1, j2 = k - i2;
                if (j1 <= m && j1 >= 1 && j2 <= m && j2 >= 1) {
                    int t = a[i1][j1];
                    if (i1 != i2) t += a[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 - 1] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }
        }
    }

    cout << f[n + m][n][n] << endl;

    return 0;
}

总结

对于动态规划问题，闫氏分析法很好用。数字三角形模型较为简单，就是根据最后一步怎么得来的，推断出状态转移方程即可解出，两次较为复杂，但其实也是对一次状态上的叠加而已（如：下下，右右，下右，右下）