#创作计划# 区间 DP

AAA逃离森林湖的蔡锡龙批发

2026-04-25 14:09:33

发布于：广东

10阅读

0回复

0点赞

前言

雷霆吗，站内居然没有好好讲区间 DP 的。
适合 DP 初学者食用。

正文

什么是区间 DP , 区间 DP 的性质

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系．
--OI Wiki ^[1]
通俗来说，区间 DP 解决一些需要合并（也有分割）子区间的题目。
在这些题目中，一般会要求你进行合并/分割操作，每次操作有一个随操作区间而变的操作价值，答案是价值和的最大/最小值。

区间DP的状态表示

我们考虑一道题，让你合并区间，每次合并有一个价值，要这个价值最大。
比如， $f(i,j)$ 表示 $[i,j]$ 区间的元素合并的最大值。
那么如何求 $f(i,j)$ 呢？
我们在 $[i,j)$ 中取一个合并点 $k$ ，这个点确定了两个区间 $[i,k],[k+1,j]$ 。
那么 $f(i,j)$ 就是：

$max(f(i,k)+f(k+1,j)+cost)$

其中 $cost$ 是合并这两个子区间的价值。
求解的时候，只需要枚举这个合并点就可以了。
对于初始状态，不同题目有不同要求，如下文例题的初始状态是没合并过，所以是 $0$ 。
答案就是操作完的值，即 $f(1,n)$ 。

例题

P1775 石子合并（弱化版） / A20908.石子合并（弱化版）

原题需要破环成链而这道简单题不用。

题目大意

给定一个包含 $N$ 个元素的序列 $m$ ，要求把这些元素进行合并操作，每次操作的代价是两个元素的和。要求使这个元素最小。

思路

把元素视为长度 $1$ 的序列，那么题目大意就是合并成长度 $n$ 的序列。
标准区间 DP 。
注意题目要最小值，所以上文转移公式的 $max$ 要变成 $min$ 。
对于长度为 $1$ ~ $n$ 的序列都要进行操作，所以要再遍历一个长度 $len (1\leq len \leq n)$ 表示当前合并区间的长度。
然后遍历一个区间开始点 $i (1\leq i \leq n-len+1)$ 即可。
代码如下：

//f(i,j) = min(f(i,k) + f(k+1,j) + cost)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
int m[314];
ll dp[314][314];//dp[i][j] -> f(i,j)
ll sum[314];
ll get_sum(int l,int r){//区间前缀和
    return sum[r]-sum[l-1];
}
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            dp[i][j]=100000000;
        }
    }

    for(int i = 1;i <= n;i++){
        cin >> m[i];//输入
        dp[i][i]=0;//初始化
        sum[i]=sum[i-1]+m[i];//前缀和方便区间和
    }
    for(int len = 2;len <= n;len ++){//长度
        for(int i = 1;i <= n - len + 1;i ++){//左端点
            int j = i + len - 1;//右端点
            for(int k = 1;k < j;k ++){//合并点
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+get_sum(i,j));//转移
            }
        }
    }
    cout << dp[1][n];
}