数字金字塔问题动态规划c语言

数字金字塔问题是一个经典的动态规划问题，它可以用来求解给定数字金字塔的最大路径和。下面是一个使用C语言实现的示例代码：

#include <stdio.h>
#define MAX_SIZE 100

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

int maxPathSum(int pyramid[MAX_SIZE][MAX_SIZE], int n) {
    // 从倒数第二行开始向上计算最大路径和
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            // 当前位置的最大路径和等于下一行相邻两个位置的较大值加上当前位置的值
            pyramid[i][j] += max(pyramid[i + 1][j], pyramid[i + 1][j + 1]);
        }
    }
    // 最终结果保存在金字塔的顶部
    return pyramid[0][0];
}

int main() {
    int n;
    printf("请输入数字金字塔的行数：");
    scanf("%d", &n);
    printf("请输入数字金字塔的元素：\n");
    int pyramid[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &pyramid[i][j]);
        }
    }
    int maxSum = maxPathSum(pyramid, n);
    printf("最大路径和为：%d\n", maxSum);
    
    return 0;
}

这段代码中，我们首先定义了一个`max`函数，用于返回两个数中的较大值。然后，我们定义了一个`maxPathSum`函数，用于计算数字金字塔的最大路径和。在`maxPathSum`函数中，我们使用两层循环来遍历金字塔的每个位置，并根据动态规划的思想计算出最大路径和。最后，在`main`函数中，我们通过用户输入构建数字金字塔，并调用`maxPathSum`函数来求解最大路径和。