区间dp问题

区间dp概述

什么是区间dp

区间dp就是在区间上进行动态规划,求解一段区间上的最优解,其主要的手段是通过合并小区间的最优解进而得出整个大区间上的最优解。

核心思路

如果是要求一个大区间上的最优解,那么就将这区间分割成一个个小区间,求解每个小区间的最优解,再合并每个小区间的最优解,从而得到大区间上的最优解即可。

所以自然在代码的实现上,可以枚举区间长度len为每次分割成的小区间(由短到长不断合并),所以问题就变成了如何穷举所有的区间的这个问题。

同时,由于一个区间的最优解是通过枚举其内的小区间来做的,因此需要枚举大区间内的每一个区间的情况。

对于区间的合并,一定存在一个分界点,这个分界点就是哪两个区间合并的界限,因此我们如果要穷举所有区间合并的情况,只需要穷举分界点即可

如何穷举所有的区间?

从一个起点出发,延伸出来的区间长度是[1+i]个,其中i∈[0,n-1],用代码来表示就是

for(int i = 1;i<=len;i++){		  //枚举长度
    for(int j = 1;j+len-1<=n;j++){//枚举起点
        int end = j + len -1;
        for(int k = j;k<end;k++){
            ...//状态转移。
        }
    }
}

我们注意到这种题目通常需要借助于两个区间的结果来得到答案,这种情况下,那么这道题就不是独立子问题了呢?

注意:划分是否是独立子问题的唯一标准是子问题之间是否会产生联系,也就是一个子问题的答案依赖于另一个子问题的答案,而这道题而言,一旦我们确定了区间长度和切分点,这时候的状态就是唯一确定的,而且左右区间互不关联,没有任何联系,因此是独立的,同时也容易知道,这个状态对应的结果也只有一个,是依赖于单个结果进行转移的,具有最优子结构没错。

经典例题:石子合并问题

1. 一行排列并且相邻合并的模型

一行排列且相邻合并有n堆石子A1,A2,...,An形成一行，

每堆石头个数记为ai(1<=i<=n)，相邻两堆可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。

这道题是动态规划的经典问题，既然是动态规划，我们应该从状态、选择这两个维度对问题进行分析。

• 状态:当前正在合并哪一堆石子?我们用一个指针i指向数组，表示当前正在合并哪两堆石子,合并石子的时候,然后我们知道，合并的时候，合并旁边的石子并不一定只是合并一堆，也就是a[i-1]或者a[i+1]，而是有可能合并一个区间内的石子，这是因为合并之后，这些石子就归成一堆了，因此我们的状态涉及到两个变量，可以这样来表示:从i...j这个区间内合并成一堆石子所能得到的得分，至于是最低得分还是最高低分，这个按照题目要求来定义即可。回推题目的过程，如果要得出答案，最终一定是dp[0][n-1] = dp[0][k] + dp[k+1][n-1]这个式子来决定的

同时容易知道，题目的最后答案应当是dp[0][n-1]:从0到n-1合并石子后所能得到的最高(最低)得分

• 选择:我们注意到，合并的最终结果是要求得到最高或者最低，这样的话就决定了我们的选择应当具有贪心性质，在每一次合并的时候，我们都希望这一次的合并能够获得的得分是最低或者最高的。那么也就决定了，我们在合并的时候可以选择和右边的合并，也可以选择和左边的合并，也可以不合并，选择的标准取决于能否得到最优解

• 状态转移:根据最终答案式:dp[0][n-1] = dp[0][k] + dp[k+1][n-1]，有所启发。

例子:假设我们有5堆石子，那么合并的方法有1 4,2 3,3 2,4 1

讨论一下base-case:

如果只有一堆石子，那么就不需要合并，花费为0

如果只有两堆石子，那么就必须要合并，花费为a[0]+a[1]

如果有三堆石子，那么合并成两堆的方法有两种

• a[0]+a[1] = A=>A+a[2]
• a[1]+a[2] = B=>B+a[0]

然后两者取最小，就是这三堆合并的最小代价

如果石子有四堆，那么我们想象一下，我们已经合并好了其中的三堆，那么我要做的就是从这合并好了的三堆中得到一个最优解，把这个最优解加上新来的石子，就可以了，同理，五堆、六堆…n堆也是一样的

我们以五堆的情况来分析一下情况，我们假设这五堆石子是1 2 3 4 5，然后我尝试第3堆石子准备要合并，那么合并的话必然是用a[0]-a[1]合并后的结果与a[2]合并，或者是用a[3]-a[4]合并后的结果与a[2]合并。如果我们想要求出最终的最优解，最简单的办法就是做一个穷举

穷举其就是穷举所有的合并情况,那么合并情况是怎么的出来的呢?

**关键就是一个倒推的思想,合并的时候肯定是两堆石头合并在一起,因此在最后的合并之前,必然存在一个分界点,假设这个分界点是k,使得左边那堆石子是[l,k],右边那堆石子是[k+1,r]**。

最后梳理一下动态规划的三要素

• 状态：合并的分界点是哪个?合并的区间长度是多少?
• 选择：是选择之前区间合并的最小值,还是在新分界点合并的最小值?
• 定义dp数组:dp[l][r],从第l堆石子合并到第r堆石子所能得到的最小代价,注意:闭区间
• 状态转移方程

//base-case
if(l == r){
    //当是同一堆石子的时候,不需要合并,因此
    dp[l][r] = 0;
}

//推广,状态转移
dp[l][r] = Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+preSump[l][r]);
//根据计算规则,就是合并[l][k]的代价+合并[k+1][r]的代价+这两堆的总重量

根据上述分析写出ac代码

//
// Created by 12743 on 2022/10/7.
//
#include <iostream>
#include <cstring>
using namespace std;
const static int N = 100+5;
int nums[N];
int dp[N][N];
int preSum[N];
class Solution {
public:
    void solve(){
        int n;cin>>n;
        //从1开始,方便做前缀和
        preSum[0] = 0;
        for(int i = 1;i<=n;i++){
            cin>>nums[i];
            preSum[i] = nums[i] + preSum[i-1];
        }
        //这个memset是为了区分记录了答案和没有记录答案的数组
        memset(dp,0x3f3f3f,sizeof dp);
        //定义dp数组,dp[l][r]:从l合并到r
        //定义base-case
        for(int i = 1;i<=n;i++){
            dp[i][i] = 0;
        }
        //枚举长度
        for(int len = 2;len<=n;len++){//长度最大为n
            //枚举起点,如果i是起点,len是区间长度,那么r是多少?
            //如果i是1,我们想要的区间长度是1,那么也就是区间只包含i这个元素
            //那么也就是从1遍历到1,那么end就是i+1-1
            //同理,如果区间长度是2,那么也就是区间包含i和i+1这个元素
            //也么也就是从1遍历到2,那么end就是i+2-1
            //...所以r = l+len-1
            for(int l = 1;l+len-1<=n;l++){
                int r = l+len-1;
                for(int k = l;k < r;k++){//为了确保k+1有元素,也就是说是右边有那一堆,因为这样我才能合并!]
                    dp[l][r] = std::min(dp[l][r],
                                        dp[l][k]+dp[k+1][r]+(preSum[r]-preSum[l-1]));
                }
            }
        }
        cout<<dp[1][n]<<endl;
    }
};

int main(){
    ios::sync_with_stdio(false);
    Solution solution;
    solution.solve();
    return 0;
}

• 如果让你求合并的最大代价,你怎么求?

同样的分析思路,如果要求区间的最大值,那么我就求子区间的最大值就可以了,只需要在决策过程中将min()改成max()即可

2. 第二个模型:一圈排列并且相邻合并

对于有环的问题,一般思路就是将数组复制一份出来接上去,另一种方案就是通过指针取模运算来得到答案

这里的话采用第一种思路比较好理解。代码如下:

void transfer(){
        //接一半数组上去,前缀和需要重新计算
        for(int i = n+1;i<=2*n;i++){
            nums[i] = nums[(i%n)];
            preSum[i] = preSum[i-1]+nums[i];
        }
    }
    void solve3(){
        memset(dp,0x3f3f3f,sizeof dp);
        //定义dp数组,dp[l][r]:从l合并到r
        //定义base-case
        for(int i = 1;i<=2*n;i++){
            dp[i][i] = 0;
        }
        //枚举长度,注意,这里不能超过n否则一堆石头就会被算两次
        for(int len = 1;len<=n;len++){//长度最大为n
            //枚举起点,如果i是起点,len是区间长度,那么r是多少?
            //如果i是1,我们想要的区间长度是1,那么也就是区间只包含i这个元素
            //那么也就是从1遍历到1,那么end就是i+1-1
            //同理,如果区间长度是2,那么也就是区间包含i和i+1这个元素
            //也么也就是从1遍历到2,那么end就是i+2-1
            //...所以r = l+len-1
            for(int l = 1;l+len<=2*n;l++){
                int r = l+len-1;
                for(int k = l;k < r;k++){//为了确保k+1有元素,也就是说是右边有那一堆,因为这样我才能合并!]
                    dp[l][r] = std::min(dp[l][r],
                                        dp[l][k]+dp[k+1][r]+(preSum[r]-preSum[l-1]));
                }
            }
        }
        int min = 0x3f3f3f;
        for(int i = 1;i<=n;i++){
            min = std::min(min,dp[i][i+n-1]);
        }
        cout<<min<<" ";
    }