数字三角形

从问题的状态表示分析，$f[i][j]$表示从起点开始到达$(i,j)$的路径。
自底向上考虑，对于第$i$层而言，状态转移方程可以表示为：
$f[i][j] = max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j])$
此时，可以直接在原数组上进行$DP$，而无需开辟额外数组来保存转移信息。
当到达最顶层时，就是问题答案。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

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 = n - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            a[i][j] = max(a[i + 1][j] + a[i][j], a[i + 1][j + 1] + a[i][j]);

    cout << a[1][1];
    return 0;
}