学习博客：https://blog.****.net/noiau/article/details/72514812
看了好久，这里整理一下证明
方程形式：dp(i,j)=min(dp(i,k)+dp(k+1,j))+cost(i,j) O(n^3)
四边形不等式：将其优化为O(n^2)
1.四边形不等式
a<b<=c<d
f(a,c)+f(b,d)<=f(b,c)+f(a,d)交叉小于包含
则对于i<i+1<=j<j+1
f(i,j)+f(i+1,j+1)<=f(i+1,j)+f(i,j+1)
f(i,j)-f(i+1,j)<=f(i,j+1)-f(i+1,j+1)
令g(j)=f(i,j)-f(i+1,j),则g(j)递增
2.若cost(i,j)有凸性，则dp(i,j)也有凸性
只需要证明对任意i<i+1<=j<j+1,有dp(i,j)+dp(i+1,j)<=dp(i+1,j)+dp(i,j+1)
设dp(i+1,j)取最优解的k=x，dp(i,j+1)取最优解的k=y
即要证：dp(i,j)+dp(i+1,j)<=dp(i,y)+dp(y+1,j+1)+dp(i+1,x)+dp(x+1,j)+cost(i,j+1)+cost(i+1,j)（1）
令A=dp(i,y)+dp(y+1,j+1)+dp(i+1,x)+dp(x+1,j)；
由于dp(i,j)的最优解不一定为k=x,则dp(i,j)<=dp(i,x)+dp(x+1,y)+cost(i,j)
同理由于dp(i+1,j)的最优解不一定为k=y,则dp(i+1,j)<=dp(i+1,y)+dp(y+1,j)+cost(i+1,j)
（1）式可化为：
dp(i,j)+dp(i+1,j)<=A+cost(i,j)+cost(i+1,j)<=A+cost(i,j+1)+cost(i+1,j)
由cost的凸性可知成立，故dp(i,j)也有凸性
3.证明决策的单调性
设s(i,j)表示dp(i,j)最优时的k值
要证：s(i,j-1)<=s(i,j)<=s(i+1,j)
先证s(i,j-1)<=s(i,j):
设y=s(i,j-1),对任意x满足x<=y<j-1<j,有x+1<=y+1<=j-1<j
由四边形不等式：dp(x+1,j-1)+dp(y+1,j)<=dp(x+1,j)+dp(y+1,j-1)
令A=dp(i,x)+cost(i,j-1)+dp(i,y)+cost(i,j)
两边同时加上A
化简得到:dp(i,j-1)(k=x时的值)+dp(i,j)(k=y)<=dp(i,j)(k=x)+dp(i,j-1)(k=y)
移项：dp(i,j-1)(k=x)-dp(i,j-1)(k=y)<=dp(i,j)(k=x)-dp(i,j)(k=y)
由于k=y时dp(i,j-1)取最小值，则左边>=0，即dp(i,j)(k=x)>=dp(i,j)(k=y)
也就是说，对于dp(i,j)，任意一个k=x<y都不如k=y优。
故s(i,j-1)<=s(i,j)
另一边同理（不证了）
那么关键就在于枚举k的部分
//s(i,j-1)<=s(i,j)<=s(i+1,j)
for(int i=n;i>=;i--)
(int j=i+;j<=n;j++)
{
int d=INF,id=;
for(int k=s[i][j-];k<=s[i+][j];k++)
{
if(d>dp[i][k]+dp[k+][j]+sum[j]-sum[i-])
{
d=dp[i][k]+dp[k][j]+sum[j]-sum[i-];
id=k;
}
}
dp[i][j]=d;
s[i][j]=id;
}
总复杂度O(n^2)
补充一个证明
来源为https://www.cnblogs.com/mlystdcall/p/6525962.html，我稍微加了一点点
对于固定的区间长度len，有
dp[i][i+len]的决策范围为s[i][i+len-1]至s[i+1][i+len]
dp[i+1][i+len+1]的决策范围为s[i+1][i+len]至s[i+2][i+len+1]
dp[i+2][i+len+2]的决策范围为s[i+2][i+len+1]至s[i+3][i+len+2]
如此脑补下去，我们发现，对于固定的区间长度len，总共的决策只有O(n)个！因为一共有O(n)个不同的区间长度len，所以算法的总复杂度就是O(n^2)！
模板题：合并石子
现在有n堆石子，要将石子按一定顺序地合成一堆，规定如下，每次只能移动相邻的两堆石子，合并费用为新和成一堆石子的数量，求把n堆石子全部合并到一起所花的最少或者最大花费
很容易想到这样一个dp转移
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+cost[i][j]
震惊！这不就是之前所讲的模型嘛？原来之前O（n^3）方的合并石子问题还可以优化（我太弱了）
首先明确一点，cost[i][j]表示把第i堆到第j堆的石子和到一起的最后一步的代价，显然，之前无论怎么合并，最后一步的代价都是一样的，所以我们可以先预处理出这个cost数组，他等于cnt[j]-cnt[i-1]，其中cnt数组是前缀和
---------------------
作者：NOIAu
来源：****
原文：https://blog.****.net/noiau/article/details/72514812
版权声明：本文为博主原创文章，转载请附上博文链接！
分析题目：
只要证明cost(i,j)满足凸性。g(j)=cost(i,j)-cost(i+1,j)=sum(j)-sum(i-1)-sum(j)+sum(i）=sum(i)-sum(i-1)与j无关，满足（此时为等于）。
我的模板：
#include<bits/stdc++.h>
using namespace std; const int N=,INF=(int)1e9;
int dp[N][N],s[N][N],sum[N]; int main()
{
//freopen("a.in","r",stdin);
int n;
scanf("%d",&n);
sum[]=;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i]=sum[i-]+x;
}
for(int i=;i<=n;i++) dp[i][i]=,s[i][i]=i;
//s(i,j-1)<=s(i,j)<=s(i+1,j)
for(int i=n;i>=;i--)
(int j=i+;j<=n;j++)
{
int d=INF,id=;
for(int k=s[i][j-];k<=s[i+][j];k++)
{
if(d>dp[i][k]+dp[k+][j]+sum[j]-sum[i-])
{
d=dp[i][k]+dp[k][j]+sum[j]-sum[i-];
id=k;
}
}
dp[i][j]=d;
s[i][j]=id;
}
printf("%d\n",dp[][n]);
return ;
}