🔍 解题思路

一道很经典的动态规划题。题意就是有一个数字三角形，从顶点（1,1）开始出发，一直走到最底层，每次只能往下走或者右下走，期间会有很多不同大小的数字，求最后走到最底层之后所经过的所有数字之和的最大值。

状态转移方程为dp[i][j] = a[i][j]（i==n时）；其他情况时：dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i][j]；

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 111;
int a[N][N], dp[N][N], n;

int main()
{
    // freopen("in.txt","r",stdin);
    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++)
        dp[n][i] = a[n][i];
    //从底层一行一行向上递推
    for(int i = n-1; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j];
    cout << dp[1][1] << endl;
    return 0;
}