c语言实现动态规划算法沙堆合并

沙堆合并是一个经典的动态规划问题。我们可以使用一个二维的数组 `dp[i][j]` 来表示合并第 `i` 堆到第 `j` 堆所需的最小代价。其中，`i` 和 `j` 都是整数，且 `1 <= i <= j <= n`，`n` 是沙堆的个数。

对于一个沙堆 `k`，它的大小为 `s[k]`，即可以用 `s[k]` 个单位的代价将其合并到其他沙堆中。因此，当 `i=j` 时，`dp[i][j]=0`；当 `i<j` 时，可以枚举一个中间点 `k`，将前半部分 `i` 到 `k` 和后半部分 `k+1` 到 `j` 合并，这样的代价为 `dp[i][k]+dp[k+1][j]+s[i]+s[i+1]+...+s[j]`，我们只需要取这些代价中的最小值即可。

下面是 C 语言的代码实现：

#include <stdio.h>
#include <limits.h>

#define MAXN 105

int n, s[MAXN], dp[MAXN][MAXN];

int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[i]+s[i+1]+...+s[j]);
            }
        }
    }
    printf("%d\n", dp[1][n]);
    return 0;
}

其中 `INT_MAX` 定义在 `limits.h` 头文件中，表示 `int` 类型的最大值。注意，将 `dp[i][j]` 初始化为 `INT_MAX` 是为了在后面的转移中取最小值时不受影响。