[复习资料.PDF]数字三角形(DP)

discription:
有一个层数为 n（n≤1000）的数字三角形（如下图）。现有一只蚂蚁从顶层开始向下走，每走
下一级时，可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值, 并记录选取的路径。
1
6 3
8 2 6
2 1 6 5
3 2 4 7 6
最大和是23, 选取1 3 6 6 7.
solution:
设\(f[i][j]\)为从点\((i,j)\)到底部的最大总和值, 则:
\(f[i][j]=max(f[i+1][j+1],f[i+1][j])+grid[i][j]\)
实现用逆推: 以层数\(i\)递减
记录每一步的选择, 可以打印最终的选择方案.\(bool型的g[i][j]\)表示点\((i,j)\)的来源,(取值1对应来自右下方向).
code:

#include<cstdio>
#include<iostream>
const int L = 1001;
using std::max;
int f[L][L], grid[L][L], n;
bool g[L][L];
void print_path(int x, int y) {
    if (x > n || y > n)return;
    printf("%d ", grid[x][y]);
    if (g[x][y])print_path(x + 1, y + 1);
    else print_path(x + 1, y);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)for (int j = 1; j <= i; ++j)scanf("%d", grid[i] + j);
    for (int i = n; i; --i)for (int j = 1; j <= i; ++j) {
        if (f[i + 1][j + 1] >= f[i + 1][j])f[i][j] = f[i + 1][j + 1] + grid[i][j], g[i][j] = 1;
        else f[i][j] = f[i + 1][j] + grid[i][j];
    }
    printf("%d\n", f[1][1]);
    print_path(1, 1);
}

[复习资料.PDF]数字三角形(DP)

原文：https://www.cnblogs.com/dwt2021/p/14402202.html