沙子合并-区间动态规划（详细注释C++）

解题思路:
1995年的经典题目，采用对区间进行动态规划的思想。

每次合并的代价为两堆沙子数量之和，那么最后一次合并的代价就是所有沙子数量之和，当合成进行最后一次合并的两堆沙子所用的代价最小时，总代价最小。

问题就变为选择某种区间划分方法，将[1,n]划分为两个大区间[1,k]和[k+1,n]，使得将[1,k]和[k+1,n]区间内的沙子分别合并为一大堆所用的代价最小。

原问题就分解为：求[1,k]，[k+1,n]区间内沙子合并的最小代价。

定义二维数组dp，dp[i][j]表示将区间[i, j]内的沙子合并所需的最小代价，最终输出dp[1][n]。

状态转移方程为：dp[i][j] = min{dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]} (k属于[i,j-1])，(sum[i]表示前i个沙子的数量之和）。
注意事项:

不能两重循环遍历区间起点和终点

B站讲解视频：
【手动模拟石子合并 讲透区间动态规划 参考闫氏分析法】 https://www.bilibili.com/video/BV1ov4y1y7et/?share_source=copy_web&vd_source=9e42598e27fab349ac2a34d5c09f3645
参考代码:

#include<iostream>
using namespace std;
#define maxn 1001
#define INF 1<<29
int dp[maxn][maxn];
int a[maxn],sum[maxn];
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=N;len++)//遍历区间长度
        for(int i=1;i<=N-len+1;i++)//遍历区间起点
        {
            int end=i+len-1,minsum=INF;
            for(int k=i;k<end;k++)//遍历区间划分
                minsum=min(minsum,dp[i][k]+dp[k+1][end]+sum[end]-sum[i-1]);
            dp[i][end]=minsum;
        }
    printf("%d",dp[1][N]);
    return 0;
}