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

数字三角形问题是指给定一个由数字组成的三角形，从顶部出发，每次只能向下走一层，经过的数字会累加，求出从顶部到底部经过的数字和最大的路径。

动态规划算法可以很好地解决这个问题，具体步骤如下：

1. 定义状态：设dp[i][j]表示从顶部出发到第i行第j列的位置的最大路径和。

2. 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]，其中triangle[i][j]表示三角形第i行第j列的数值。

3. 边界条件：dp[0][0] = triangle[0][0]，即从顶部出发到顶部位置的最大路径和就是顶部位置的数值。

4. 最终结果：从底部一行中所有位置的dp值中取最大值，即为从顶部到底部的最大路径和。

以下是C语言代码实现：

#include <stdio.h>
#define MAX_N 100

int triangle[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

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

int main() {
    int n;
    scanf("%d", &n);

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

    // 动态规划
    dp[0][0] = triangle[0][0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            } else if (j == i) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
            }
        }
    }

    // 输出结果
    int max_sum = 0;
    for (int i = 0; i < n; i++) {
        if (dp[n-1][i] > max_sum) {
            max_sum = dp[n-1][i];
        }
    }
    printf("%d\n", max_sum);

    return 0;
}