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

动态规划数字三角形，也称为杨辉三角，是一个经典的动态规划问题，其基本思路是：从底层开始，逐层计算每个数字的最优解，并将最优解存储在一个二维数组中，最终得到整个数字三角形的最优解。

具体实现方法如下：

1. 定义一个二维数组dp，dp[i][j]表示从(i,j)位置出发到底层的最优解。

2. 初始化dp数组，将dp数组最后一行的值初始化为数字三角形的最后一行。

3. 从倒数第二行开始，逐层计算每个位置的最优解，即dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]，其中triangle[i][j]表示数字三角形中的数字。

4. 最终，dp[0][0]即为数字三角形的最优解。

下面是具体的代码实现：

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int j = 0; j < n; j++) {
        dp[n-1][j] = triangle[n-1][j];
    }
    for(int i = n-2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
        }
    }
    return dp[0][0];
}

该算法的时间复杂度为O(n^2)，空间复杂度为O(n^2)，其中n为数字三角形的行数。