动态规划数字三角形代码

动态规划数字三角形是一个经典的动态规划问题，它是指给定一个由数字组成的三角形，从三角形的顶部出发，在每一步可以选择向下走或者向右下走，一直走到三角形底部，求出从顶部到底部路径上的数字之和最小的路径。

以下是动态规划数字三角形的代码实现：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100 + 10;
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] = min(dp[i+1][j], dp[i+1][j+1]) + a[i][j];
    cout << dp << endl;
    return 0;
}

其中 `dp[i][j]` 表示从第 `i` 行第 `j` 列出发到底部路径上的数字之和最小值，`a[i][j]` 表示三角形第 `i` 行第 `j` 列的数字，因为只需要考虑相邻两行之间的关系，所以可以使用滚动数组对空间进行优化。