洛谷 P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

题目连接：https://www.luogu.com.cn/problem/P1216

这一题是一道线性DP，可以从上往下求解，也可以从下往上求解

第一种做法，从上往下求解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;int n;
int a[N][N];int main(){
    cin >> n;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= i; j ++ ) cin >> a[i][j];for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);int res = 0;for (int i = 1; i <= n;  i++ ) res = max(res, a[n][i]);cout << res << endl;return 0;
}

从下往上

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;int n;
int a[N][N], f[N][N];int main(){
    cin >> n;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= i; j ++ )cin >> a[i][j];for (int i = n - 1; i >= 1; i -- )for (int j = i; j >= 1; j -- )a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);cout << a[1][1] << endl;return 0;
}