用动态规划算法解决数字三角形问题 c语言

数字三角形问题是一个经典的动态规划问题。假设输入的数字三角形为一个二维数组`triangle`，其中`triangle[i][j]`表示第`i`行第`j`列的数字。在该数字三角形中，每个数字只能向下或向右下方移动，要求从顶部到底部的路径上数字之和最大。

动态规划的思路是从底向上逐层计算每个数字的最优解，最终得到顶部到底部的路径上数字之和的最大值。具体算法步骤如下：

1. 从数字三角形的底部开始，将底部每个数字作为子问题的最优解。即`dp[i][j] = triangle[i][j]`。
2. 从倒数第二行开始，对于每个数字`triangle[i][j]`，计算出它到底部路径上的最优解，即`dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])`。
3. 最终得到的`dp[0][0]`即为顶部到底部的路径上数字之和的最大值。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h> 

int main() {
    int n; // 数字三角形的行数
    scanf("%d", &n);

    int triangle[n][n]; // 存储数字三角形
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &triangle[i][j]);
        }
    }

    int dp[n][n]; // 存储每个数字的最优解
    for (int i = 0; i < n; i++) {
        dp[n-1][i] = triangle[n-1][i]; // 底部数字的最优解为它本身
    }
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1]); // 计算每个数字的最优解
        }
    }

    printf("%d", dp[0][0]); // 输出顶部到底部的路径上数字之和的最大值

    return 0;
}

其中，`max()`函数为C语言内置的求最大值的函数，可以使用以下代码实现：

int max(int a, int b) {
    return a > b ? a : b;
}