如何高效制作学习笔记区间DP？

本文共计2924个文字，预计阅读时间需要12分钟。

嘿嘿，区间DP引入，区间DP，其实和普通的DP差别不大。但和普通DP不同的是，它以一个区间的长度为阶段。一开始，我们知道长度为(1)的区间的值(即元区间的值，也就是单点)。当然，也可能有‘可能’‘嘿嘿。

咕咕。。。 区间 DP 引入

区间 DP，其实和普通的 DP 差不多。但是和普通 DP 不一样的是，它以一个区间的长度为阶段。一开始，我们知道长度为 \(1\) 的区间的值（即元区间，当然也可能知道长度 \(> 1\) 的某些区间的值），而我们就可以通过这些元区间来推出更长的区间的值，最后得到整个区间的值。

一般来讲，我们会定义状态 \(f_{i, j}\) 来表示下标为 \(i \sim j\) 的元素（即区间 \([i, j]\)）。

PS：假如是习题说明我懒得写 TJ 了，以后再写。

经典例题 「例题」 石子合并无环版

原题目链接：Link。

首先，我们定义 \(f_{i, j}\) 表示把下标为 \(i \sim j\) 的石子合并成一堆石子的代价。显然，一堆石子不需要合并，所以 \(f_{i, i} = 0\)。

因为每次只能选相邻的 \(2\) 堆石子合并成新的一堆，我们于是可以枚举一个中间点 \(k\)，从 \(k\) 分开成左右两堆，并把这两堆石子合并，代价是把这两堆石子分别合并的代价加上两堆石子数之和。