C用动态规划算法编程实现数字三角形问题

数字三角形问题是一个经典的动态规划问题。题目描述如下：

给定一个由整数组成的三角形，从顶部出发，每次可以向下走一格或者向右下走一格，一直走到底部，求出一条路径，使得路径上经过的数字之和最大。

下面是C语言的动态规划算法实现：

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

#define N 100

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

int main()
{
    int n;
    int dp[N][N]; // dp[i][j]表示从三角形顶部走到第i行第j列的最大数字和
    int triangle[N][N];

    printf("请输入数字三角形的行数：");
    scanf("%d", &n);

    printf("请输入数字三角形：\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &triangle[i][j]);
        }
    }

    memset(dp, 0, sizeof(dp)); // 初始化dp数组

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]; // 状态转移方程
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[n][i]); // 找到最大值
    }
    printf("最大数字和为：%d\n", ans);

    return 0;
}

在上面的代码中，我们使用了一个二维数组`dp[N][N]`来表示从三角形顶部走到第i行第j列的最大数字和。对于每个位置`(i,j)`，我们可以选择从它上面的位置`(i-1,j)`或者`(i-1,j-1)`转移过来，然后再加上当前位置的数字`triangle[i][j]`，即可得到从顶部走到当前位置的最大数字和。状态转移方程为：`dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]`。

最后，我们遍历最后一行的所有位置，找到最大值即可得到最大数字和。