区间DP石子合并问题 & 四边形不等式优化

入门区间DP，第一个问题就是线性的规模小的石子合并问题

dp数组的含义是第i堆到第j堆进行合并的最优值

就是说dp[i][j]可以由dp[i][k]和dp[k+1][j]转移过来

状态转移方程 dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + sum[i][j]) 对于第i堆到第j堆合并的花费 他的子问题是第i个的合并顺序

op1：k实际上控制的是第i堆也就是起始堆的合并顺序 因为必须是相邻合并dp[i][i] 先合并dp[i+1][j]最后再来合并第i堆 dp[i][i+1]  && dp[i+2][j] 就是分开合并i 和i + 1堆，i+2和j之间所有的堆，最后+tmp作整体合并 ok got it!

/*
入门问题——取石子
每次只能合并相邻的一堆
求最小花费
dp[i][j] 常常用来表示i到j这个区间的最优值是多少
也就是说dp[i][j]可以由dp[i][k]和dp[k+1][j]转移过来状态转移方程
dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + sum[i][j])
对于第i堆到第j堆合并的花费
他的子问题是第i个的合并顺序
op1：k实际山控制的是第i堆也就是起始堆的合并顺序
因为必须是相邻合并dp[i][i] 先合并dp[i+1][j]最后再来合并第i堆
dp[i][i+1]  && dp[i+2][j]
就是分开合并i 和i + 1堆，i+2和j之间所有的堆，最后+tmp作整体合并
ok got it!*/#include <iostream>
#include <cstdio>
#include <string.h>
#define inf 1e8 + 1e7
using namespace std;
const int maxn = 1e3 + 1e1;
int dp[maxn][maxn],sum[maxn];
int a[maxn];
//由sum[i][j]表示第i堆石子到第j堆石子全部合并的总石子量。
//dp[i][j]为第i堆石子到第j堆合并的花费
int getMinval(int n)
{
    memset(dp,0,sizeof(dp));
    for(int v = 1;v < n;v++)//第一维：循环控制合并堆的长度从长度2开始
        for(int i = 0;i < n-v;i++)//起点
    {
        int j = i + v;//终点
        dp[i][j] = inf;//仅仅一次初始化的机会，所以可以在里面进行初始化
        int tmp = sum[j] - (i > 0 ? sum[i - 1] : 0);//求取i-j中合并的最后一次花费
        for(int k = i;k < j;k++)
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + tmp);    }
    return dp[0][n-1];
}int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&a[i]);
        }
        sum[0] = a[0];
        //sum[i] 表示从1-i堆中石子的总个数
        for(int i = 1;i < n;i++)
            sum[i] = sum[i-1] + a[i];
        printf("%d\n",getMinval(n));
    }
    return 0;
}

数据量稍微大一些的就不能用n3的复杂度来进行计算了

于是我们找到了数学优化公式——四边形不等式优化法则

先来说结论，优化的地方是对k的寻找，最优值k

如果零s[i][j] 来表示dp[i][j]取得最优值时候的k值，那么k的取值范围是{s[i][j-1],s[i+1][j]}

关于证明看了很多博客了，这里有一篇博客不错，拿来引用一下

https://blog.csdn.net/NOIAu/article/details/72514812

核心如下

~PART ONE 交叉小于包含对于（ a < b <= c< d ）如果有f[a][c]+f[b][d]<=f[b][c]+f[a][d](可以理解为一句话，交叉小于包含，即交叉的两个区间，a到c和b到d的值满足小于等于包含的两个区间[bc包含于ad])
则说这个东西满足四边形不等式，当然这个东西可能是dp数组，也可以是其他数组，比如引入里提到的cost数组，表示的是i到j的花费（比如合并石子问题）给出两个定理：1、如果上述的w函数同时满足区间包含单调性和四边形不等式性质，那么函数dp也满足四边形不等式性质
 我们再定义s(i,j)表示 dp(i,j) 取得最优值时对应的下标（即 i≤k≤j 时，k 处的 dp 值最大，则 s(i,j)=k此时有如下定理
2、假如dp(i,j)满足四边形不等式，那么s(i,j)单调，即 s(i,j)≤s(i,j+1)≤s(i+1,j+1)
如果不知道为什么，没有关系，反正后面都要证明

具证明过程，有兴趣的可以去看看上面大佬的博客

dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + cost[i][j]}

对于代价数组cost[i][j]要进行证明其符合四边形不等式：cost[i][j]+cost[i+1][j+1]<=cost[i+1][j]+cost[i][j+1]

对于所有的i，j，令其满足i< i+1<=j< j+1
我们需要证明
cost[i][j]+cost[i+1][j+1]<=cost[i+1][j]+cost[i][j+1]
移项
cost[i][j]-cost[i+1][j]<=cost[i][j+1]-cost[i+1][j+1]
令f（j）=cost[i][j]-cost[i+1][j]
f（j）=cnt[j]-cnt[i-1]-(cnt[j]-cnt[i])
f（j）=cnt[i]-cnt[i-1]
都跟j无关了，自然一定满足四边形不等式（这个时候是直接等于了，但没有违反四边形不等式）

同理证明dp数组的满足性

要推导dp[i][j]的凸性，自然要满足对任意的i，j，令i< i+1<=j< j+1 有如下结论 dp[i][j]+dp[i+1][j+1]<=dp[i+1][j]+dp[i][j+1] 令dp[i+1][j]取得最优值的时候k=x 令dp[i][j+1]取得最优值的时候k=y 令x < =y(之后还要令x > y，这里不再赘述，读者如有兴趣可以自行推导，方式相似) 将k=x代入dp[i][j]，k=y代入dp[i+1][j+1] 左式=dp[i][x]+dp[x+1][j]+cost[i][j]+dp[i+1][y]+dp[y+1][j+1]+cost[i+1][j+1]① 而对于i< i+1<=j< j+1 由于已经在壹中证明了cost的凸性，所以 cost[i][j]+cost[i+1][j+1]<=cost[i+1][j]+cost[i][j+1]② 我们会发现这个不等式的左边在①式中出现过，所以把②式中的左式和右式替换一下可以得到如下结论 dp[i][x]+dp[x+1][j]+cost[i][j]+dp[i+1][y]+dp[y+1][j+1]+cost[i+1][j+1] < =

dp[i][x]+dp[x+1][j+1]+cost[i][j+1]+dp[i+1][y]+dp[y+1][j]+cost[i+1][j]

即dp[i][j]+dp[i+1][j+1]<=dp[i][j+1]+dp[i+1][j] 证毕

最后来看决策函数的满足性（s[i][j] = k）

现在我们已经证明了cost数组和dp数组的凸性，要证明决策单调以证明优化的正确性 即要证明s[i][j-1]<=s[i][j]<=s[i+1][j] 对于s[i][j-1]<=s[i][j] 令dp[i][j-1]取得最小值时的k=y，对于所有x≠y，令x<=y 可以有如下推导 ∵x+1<=y+1<=j-1< j 四边形不等式有： dp[x+1][j-1]+dp[y+1][j]<=dp[y+1][j-1]+dp[x+1][j]

在式子两边同时加上dp[i][x]+cost[i][j-1]+dp[i][y]+cost[i][j]     可以得到

dp[i][x]+dp[x+1][j-1]+cost[i][j-1]+dp[i][y]+dp[y+1][j]+cost[i][j] < = dp[i][x]+dp[x+1][j]+cost[i][j]+dp[i][y]+dp[y+1][j-1]+cost[i][j-1]

dp[i][j-1]+dp[i][j]<=dp[i][j]+dp[i][j-1] (k=x)…………(k=y)……(k=x)……(k=y) 移项

dp[i][j-1]-dp[i][j-1]<=dp[i][j]-dp[i][j] (k=x)…………(k=y)……(k=x)……(k=y)

由于我们是令k=y时dp[i][j-1]取得最小值，那么dp[i][j-1] (k=x)一定大于等于dp[i][j-1] (k=y)，所以左式大于零，所以右式也大于零，所以对于dp[i][j-1]可以取到最优值的y，所有小于它的值，对于dp[i][j]来说，都没有y优，所以最优决策一定不是小于y的，如果令s[i][j]表示dp[i][j]取得最优值的时候的k值，那么一定有 s[i][j-1]<=s[i][j] 证毕

所以我们就可以对代码进行优化，得到如下的解决过程

#include <iostream>
#include <cstdio>
#include <string.h>
#define inf 1e8 + 1e7;
using namespace std;
const int maxn = 1e4 + 1e1;
int dp[maxn][maxn],s[maxn][maxn],cnt[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(cnt,0,sizeof(cnt));
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&cnt[i]);
            cnt[i] = cnt[i-1] + cnt[i];
        }
        for(int i = 0;i <= n;i++)
        {
            dp[i][i] = 0;
            s[i][i] = i;
        }
        for(int i = n;i >= 1;i--)//从上到下进行铺垫，因为高决策范围为s[i+1][j]
        {
            for(int j = i + 1;j <= n;j++)//从下到上进行铺垫因为，低决策范围需要s[i][j-1]
            {
                //有过疑问：为什么从i+1开始，这不废话，直线型的dp，i到j的最优值问题，区间问题。。。
                int tmp = inf;
                int te;
                for(int k = s[i][j-1];k <= s[i+1][j];k++)//取最优决策集合//这样的性质是这个不等式拥有的，他的最优解就是这样单调的
                {
                    if(tmp > dp[i][k] + dp[k+1][j] + cnt[j] - cnt[i-1])
                    {
                        tmp = dp[i][k] + dp[k+1][j] + cnt[j] - cnt[i-1];
                        te = k;
                    }
                }
                dp[i][j] = tmp;
                s[i][j] = te;
            }
        }
        cout<<dp[1][n]<<endl;
    }
    return 0;
}