（持续更新）
区间dp：顾名思义就是在区间上进行动态规划，通过合并小区间求解一段区间上的最优解。
常见模板：
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=be;j<en;j++){//割点
dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+割点代价);
}
}
}
http://www.51nod.com/Challenge/Problem.html#!#problemId=1021
第1行：N（2 <= N <= 100) 第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000)
输出最小合并代价
4
1
2
3
4
19
解题思路：很明显割点代价为前缀和：sum【en】-sum【be-1】//en为该区间的终点，be为起点
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ri register int
typedef long long ll;
inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
inline void output(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch==‘-‘){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-‘0‘,ch=getchar();
x=x*f;
}
const int maxn=105;
ll dp[maxn][maxn];
ll sum[maxn];
ll a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[i+1]=sum[i]+a[i];
}
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
dp[i][j]=1e18;
}
}
for(int i=0;i<maxn;i++){
dp[i][i]=0;
}
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=be;j<en;j++){//割点
dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1]);
}
}
}
cout<<dp[1][n];
return 0;
}
原文：https://www.cnblogs.com/Zhi-71/p/10611042.html