前言
今天我们学习另一种DP——区间DP。

程序设计思路
（由于无法从概念上描述题意，这里直接放题目~）

题意很好理解，要求我们求出合并所有石堆的最小代价。
首先思考一维DP式，很容易想到将dp[i]定义为合并从第一堆石子到第i堆石子所花费的代价。但是，状态转移方程怎么办？！由于本题中合并的顺序不唯一，第一堆石子也有可能最后合并，所以这个方法不可行。
这个时候我们需要思考一下：某个区间的最小代价一定是这个区间分为2个区间后这两个区间的代价之和。这样我们可以得到二维DP的定义：dpi代表从第i堆到第j堆石子合并所需要的最小代价。然后再思考，不难得到：我们可以对某个区间进行分割，这个分割点就是我们要去找的。故我们可以列出以下方程：dpi=min(dpi,dpi+dpi+k+1+s[j]-s[i-1]（s[i]为从第一堆石子到第i堆石子代价的前缀和，用来累加代价，自行理解，另外需要预处理）。最后一个问题：dpi如何初始化？首先如果只有一堆那合并的代价为0，故dpi=0，而由于我们求最小代价，dp[i]j可以初始化成一个很大的数，方便比较操作。

代码实现

#include <stdio.h>
#include <memory.h>
//今天想重温一下C语言，故用C语言
int n,m[1001],dp[1001][1001],s[1001];//均如题意或已讲解

int min(int a,int b){//C语言没有min函数，所以手搓一个
    if(a<b) return a;
    else return b;
}

main(){
    scanf("%d",&n);
    memset(s,0,sizeof(s));
    memset(dp,0x3f3f3f3f,sizeof(dp));//初始化为大数
    for(int i=1;i<=n;i++) dp[i][i]=0;
    for(int i=1;i<=n;i++) scanf("%d",&m[i]);
    for(int i=1;i<=n;i++) s[i]=m[i]+s[i-1];//计算前缀和
    for(int len=1;len<=n;len++) for(int i=1;i<=n;i++){//len为长度，先计算长度为1的区间之后逐渐累加并重叠
        int j=i+len-1;
        if(j>n) break;//防越界
        for(int k=0;k<len;k++) dp[i][j]=min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+s[j]-s[i-1]);//dp式
    }
    printf("%d",dp[1][n]);
    return 0;
}

可以看到，区间DP的代码很简洁，所以重在理解~

结语
区间DP没有变式，其O(n3)的时间复杂度也无法进行优化，理解即可。我是faryou，再见！