动态规划数字三角形c++

动态规划数字三角形的C++代码如下所示：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];
int a[MAXN][MAXN];

int main()
{
    int n;
    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;
}

该程序使用二维数组 `dp` 存储每个位置的最大值，其中 `dp[i][j]` 表示第 `i` 行第 `j` 列的最大值。程序从倒数第二行开始，依次计算每个位置的最大值，最后输出第一行第一列的最大值即可。