【基础】数字三角形c++

数字三角形是一个经典的算法题目，主要思路是动态规划。以下是一个简单的 C++ 实现。

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

const int MAXN = 1005;
int a[MAXN][MAXN], dp[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 j = 1; j <= n; ++j) {
        dp[n][j] = a[n][j];
    }
    // 动态规划
    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;
}

这段代码使用了两个二维数组 `a` 和 `dp`，其中 `a[i][j]` 表示数字三角形第 `i` 行第 `j` 列的数，`dp[i][j]` 表示从第 `i` 行第 `j` 列开始到底部的最大和。

首先输入数字三角形的数值，然后初始化 `dp` 数组为最后一行的数值。接着从倒数第二行开始，计算每个位置到底部的最大和，并将结果存储在 `dp` 数组中。最终输出 `dp[1][1]` 就是数字三角形的最大和。

这个算法的时间复杂度是 $O(n^2)$，可以通过本题。