区间DP详解

FTAC · 2025-05-13 00:04:49 · 算法·理论

哈喽大家好，我是 doooge，今天给大家带来的是 区间DP 的详解。

1.什么是区间DP

区间DP 是动态规划的一部分。

1.1 dp_{i,j} 的含义

所谓 区间DP，也就是 dp 数组 dp_{i,j} 表示的是一个区间的答案，比如说 dp_{2,5} 表示的就是 [2,5] 这个区间的答案，dp_{3,7} 表示的就是 [3,7] 这个区间的答案。

而且，dp_{i,j} 只能由它的子区间转移而来，也就像下图这样：

是不是很简单？那我们应该用怎样的顺序去遍历 i,j 使得在 [i,j] 的子区间一定在遍历到 [i,j] 前全部推完呢？

1.2 区间DP的遍历方式

我们可以枚举长度遍历。比如说，我们在遍历到 i,j 时，长度在 j-i+1 以下的区间一定会被遍历掉，可以看下图理解：

遍历的代码也很好写：

for(int l=1;l<=n;l++){//遍历长度
    for(int i=1;i<=n-l+1;i++){//枚举左端点
        int j=i+l-1;//求出右端点
        //dp[i][j]=...
    }
}

1.3 DP推出的结果在哪

这个其实很好猜，根据我们以往的经验，一维 dp 的答案一般是最后遍历到的第 n 位 dp_n，那么区间DP 的答案应该就是我们最后遍历到的区间，也就是长度最长的区间 dp_{1,n} 这里。

当然，也有特例，当题目要你求所有状态之和时，这时答案就不太可能是 dp_{1,n} 了，而是每个区间的答案之和，用公式表达就是：

也可以是：

当然这两个求和公式的本质都是一样的，遍历每个区间，只是遍历方式的不同而已。

2.区间dp的例题

2.1 T1:P1775 石子合并（弱化版）

有 N 堆石子排成一排，每堆石子有一定的质量 m_i。现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。试找出一种合理的方法，使总的代价最小，并输出最小代价。