区间及其他类型 | Civilization Museum

type

status

password

date

slug

summary

Matrix Multiplication

题解一

自顶向下

自底向上

自底向上-状态压缩

1000. 合并石头的最低成本

有 N 堆石头排成一排，第堆中有块石头。每次移动（move）需要将连续的堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。

示例 1：输入：stones = [3,2,4,1], K = 2 输出：20 解释：从 [3, 2, 4, 1] 开始。合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。合并 [4, 1]，成本为 5，剩下 [5, 5]。合并 [5, 5]，成本为 10，剩下 [10]。总成本 20，这是可能的最小值。

题解一

假如合并两堆

这道题是一道经典的区间dp问题，旨在通过动态规划去求一个区间的最优解，通过将大区间划分为很多个小区间，再由小区间的解来组合出大区间的解。

定义状态：为区间的最优解。左闭右闭区间。

边界条件：，初始时合并每堆数组的代价为0；其余为正无穷。

状态转移方程：选取之间的一个分界点，分别计算和的最优解，从而组合出的最优解。

其中为从第堆石子到第堆石子的花费。

注意：由于要求的是从第 1 堆到第 堆石子 dp[1,n]，所以必须从大往小遍历，必须从小往大遍历。这样在状态转移方程中利用的就是已求解的dp状态。

合并k堆

再来考虑一次合并k堆的情况。最后一定是变成k堆石头，这一步合并的成本依然是这k堆石头数目之和，也即所有石头数目之和。

我们对所有石头进行划分，左部分最终要合并成堆，而右部分最终要合并为堆。这样左部分就是一个子问题，而右部分又是一个变相的子问题（将它也继续划分为两部分来求解）。

状态：定义为合并第堆到第堆石头为堆的成本。

初始化。对于无法实现的情况，定义。

状态转移方程：

。不能直接求出合并为1堆的成本，得先合并成堆。
。这里为堆数，不能直接用是因为右部分的存在，要对右部分继续划分求解的话，子问题就必须有合并成堆的情况。

答案就是。

细节

第一点：一定会有不能合并成1堆的情况，怎么排除掉这种情况呢？

如果能合并成1堆，就一定得先合并成k堆，这在前面已经讨论过了。合并k堆石头之后，会将k堆石头变为1堆石头，那么总的石头堆数就是减少了k - 1堆。这样一直套娃，就能还原到原始的堆数n。我们由此可以定义一个方程：，是一个大于等于0的整数。

第二点：为什么划分的方式是左部分合并成1堆，右部分合并成k-1堆？左部分k-1，右部分1；左部分2，右部分k-2...这些方式可行吗？ 左右不重要，可行的划分方式只能是 和。

首先说明和能完整覆盖到所有情况：如果对于，它的最优划分是，那么，为最优划分点。代入一下，就有。后面那俩合并一下就是堆的情况，所以说1和k-1的划分方式是正确的。
再说明为什么和的划分是错误的：这一点要从递归的角度，自顶向下地来看就好理解。我们要求解的是，由于堆数为1，所以会递归调用。堆数为，需要进行划分来求解，分别调用和，从到循环。当和时我们都知道结果，但当呢？不是一个初始状态，也不是可以划分的状态，也不知道是不是合法的状态，这就变成了一个无法求解的状态，所以划分是错误的。再回到dp的角度，其实也就是是无法求解的，合并成 2 堆不是一个子问题，而我们定义的划分方式又导致它无法继续分解为子问题，那它就肯定无法求解了。

第三点：枚举分界点时，step应该是而不是1。 step为1当然也是正确的，但是却进行了很多无用的计算，导致运行时间增加。为什么step可以是k-1呢？因为我们设计的划分是每次将左部分区间合并为1堆，由合并条件，就可以知道step应该是k-1，这样会涵盖所有有效的分界点p。对于其他的分界点p，左部分不能合并为1堆，那这样的划分并没有意义，对于计算答案也就没有帮助了。

自顶向下

自底向上

312. 戳气球

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第个气球，你可以获得枚硬币。这里的和代表和相邻的两个气球的序号。如果或超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。

示例 1：输入：nums = [3,1,5,8] 输出：167 解释： nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins =

题解一

状态：表示填满开区间能得到的最多硬币数。为什么是开区间，因为戳破左右边界的时候只有一个气球，此刻需要在边界进行补1.

边界条件：表示开区间，所以区间内至少有一个值，即。那么对于，此时有。

状态转移方程：气球的编号是 0 到 n - 1，将其修改为从 1 到 n。因为表示填满开区间，所以计算戳破气球从编号 1 到 n 能得到的最多硬币数，就是。设在开区间最后戳破的气球是，此刻气球和气球还存在；此时获得的硬币数是。其中因为是开区间

最终答案即为。实现时要注意到动态规划的次序。

自顶向下

自底向上

Split String

题解一

自顶向下

自底向上

自底向上-状态压缩

87. 扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止。

如果字符串的长度 > 1 ，执行下述步骤：

在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。

随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。给你两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：输入：s1 = "great", s2 = "rgeat" 输出：true 解释：s1 上可能发生的一种情形是： "great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串 "gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」 "gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割 "g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」 "r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t" "r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」算法终止，结果字符串和 s2 相同，都是 "rgeat" 这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

题解一

给定两个字符串和，假设是由变换而来。

如果和长度不一样，或者字符串与的字符数目不同 (例如 T=aaa、S=bbb，T中a出现的次数是3，S中为0)，必定不能变来。

如果长度一样，顶层字符串能够划分为和，同样字符串也能够划分为和

情况一：没交换，，
情况二：交换了，，

子问题就是分别讨论两种情况，是否由变来，是否由变来，或是否由变来，是否由变来。

状态：表示字符串与是否是扰乱字符串。

初始条件：如果和长度不一样，或者字符串与的字符数目不同 (例如 s1=aaa、s2=bbb，s1中a出现的次数是3，S2中为0)，则返回；如果与相等，则返回。

状态转移方程：设和的长度为，我们用表示从从第个字符（从 0 开始编号）开始，长度为的子串。由于分割出的两个字符串不能为空串，那么其中一个字符串就是，另一个字符串是。我们将上面两种状态转移方程用或运算拼在一起，即可得到最终的状态转移方程。

情况一：没交换，，

其中表示与运算，即和分割出的两对字符串都要是扰乱字符串的；表示或运算，即只要有一种满足要求的分割方法，和就是扰乱字符串。

情况二：交换了，，

我们将上面两种状态转移方程用或运算拼在一起，即可得到最终的状态转移方程。