数塔用c语言怎么做啊

2.数塔dp-A
【问题描述】
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最小是多少?

已经告诉你了，这是个DP的题目，你能AC吗?
【输入形式】
输入数据首先包括一个整数C.表示测试实例的个数，每个测试实例的第一行是一个整数N(1<=N<-100),
表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
【输出形式】
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
【样例输入】
1
5
7
3 8
8 1 0
2 7 4 4
4 5 26 5
【样例输出】
17
【样例说明】
【评分标准】

按照我的理解，题目描述中的数塔可以看作一个二维数组，每个元素表示从该位置能够走到的下一层的两个数字。可以使用动态规划算法来解决该问题，具体思路如下：

首先将数塔存储到一个二维数组 a[][] 中，其中 a[i][j] 表示第 i 行第 j 列的数字。
创建一个与数塔等高的二维数组 dp[][]，其中 dp[i][j] 表示从数塔顶部到第 i 行第 j 列时的最小数字和。
初始化 dp[1][1] = a[1][1]，并对 dp[][] 数组的第一行和第一列进行初始化（因为它们只有一条路径可走，所以直接赋值）。
对于第 i 行第 j 列的元素，其最小数字和由其上一层的两个相邻元素中较小值加上当前元素的值得到，即 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + a[i][j]。
最终结果即为 dp[n][m]，其中 n 为数塔的高度，m 为最后一行的元素个数。

以下是该算法的C语言代码实现：

#include <stdio.h>
#define MAX_N 100

int a[MAX_N+1][MAX_N+1], dp[MAX_N+1][MAX_N+1];

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                scanf("%d", &a[i][j]);
            }
        }

        // 初始化第一行和第一列
        dp[1][1] = a[1][1];
        for (int i = 2; i <= n; i++) {
            dp[i][1] = dp[i-1][1] + a[i][1];
            dp[i][i] = dp[i-1][i-1] + a[i][i];
        }

        // 动态规划计算
        for (int i = 3; i <= n; i++) {  // 从第3行开始计算，因为第1行和第2行已经被初始化
            for (int j = 2; j <= i-1; j++) {
                dp[i][j] = (dp[i-1][j-1] < dp[i-1][j]) ? dp[i-1][j-1] : dp[i-1][j];
                dp[i][j] += a[i][j];
            }
        }

        // 找出最小值
        int ans = dp[n][1];
        for (int i = 2; i <= n; i++) {
            if (dp[n][i] < ans) {
                ans = dp[n][i];
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}

关于算法里我所使用的三层循环的含义，这里解释一下

最外层的循环用于处理每个测试实例。
第二层循环用于读入数塔，并对 dp[][] 数组进行初始化。
第三层循环用于动态规划计算，以及找出最小值。
在测试用例较多或者数据较大时，可以添加一些优化，如使用滚动数组来减少空间开销，或者将第三层循环修改为从右往左遍历，使得可以省略一些条件语句。
如果对你有所帮助的话，请给我一个采纳哦，谢谢啦

仅供参考，谢谢！

#include<stdio.h>

int getminsum(int **p, int n)
{
    int (*p0)[n] = p;
    int sum = *(*p0 + 0);
    int min = 0;
    int i, j = 0;
    for (i = 1; i < n; i++)
    {
        if (p0[i][j] < p0[i][j + 1])
        {
            sum += p0[i][j];
        }
        else
        {
            sum += p0[i][j++ + 1];
        }

    }
    return sum;
}

int main(void)
{
    int C, N;
    scanf("%d%d", &C, &N);
    int arr[C][N][N], sum[C];
    for (int i = 0; i < C; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k <= j; k++)
            {
                scanf("%d", &arr[i][j][k]);
            }
        }
    }

    for (int i = 0; i < C; i++)
    {
        printf("%d\n", getminsum(arr[i], N));
    }

    return 0;
}

数塔 用c语言怎么做啊

数塔用c语言怎么做啊