石子归并问题：设有n堆石子排成一排，其编号为1，2，3，…，n（n≤100)每堆石子有一定的数量，如下13，7，8，16，21，4，18。现在要将n堆石子归并成一堆。每次只能将相邻的两堆石子堆成一堆，这样经过n一1次归并之后最后成为一堆，如上面7堆沙子，可以有多种方法归并成一堆，用c++采用动态规划的算法写一段代码求出合并代价总和最小的方案，并对代码算法进行解释

好的，下面是C++代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;

int a[N], sum[N];
int dp[N][N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        dp[i][i] = 0;
    }

    for (int len = 2; len <= n; len ++ )
    {
        for (int i = 1; i + len - 1 <= n; i ++ )
        {
            int j = i + len - 1;
            dp[i][j] = 1e9;
            for (int k = i; k < j; k ++ )
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
        }
    }

    cout << dp[1][n] << endl;

    return 0;
}

算法解释如下：

对于这道问题，我们可以使用动态规划来解决。我们可以定义dp[i][j]为将第i~j个石子堆合并成一堆的最小代价。显然，当i==j时，dp[i][j]=0。

对于其他情况，我们可以枚举最后一次合并的位置k（i<=k<j），将第i~k个石子堆合并成一堆，将第k+1~j个石子堆合并成一堆，最后将这两堆合并成一堆。这样的代价就是dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]，其中sum[i]表示前i个石子堆的石子数的前缀和。

最终答案就是dp[1][n]。我们可以用类似于填表格的方式来计算dp数组，从小到大枚举区间长度和起点即可，时间复杂度为O(n^3)。

由于数据范围较小，这个算法是可以通过此题的。