动态规划练习题 | LianoのBlog

AI summary

type

status

date

slug

summary

打家劫舍问题模式

解决智力问题

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择解决或者跳过操作。解决问题 i 将让你获得 pointsi 的分数，但是你将无法解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。

和打家劫舍基本一样的问题。但是这里需要反向定义 dp[i] 表示题目 i 开始到最后的最大得分，因为状态转移方程需要 brainpoweri 向前传递。代码如下：

统计放置房子的方式数

一条街道上共有 n * 2 个地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 10^9 + 7 取余后再返回。

因为两侧的房屋互不影响，所以分别考虑两侧，最后结果就是两侧方案数的乘积。

定义 dp[i] 表示从地块 i 到 n 的方案数。

最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：
一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

和打家劫舍几乎一样，198 题是让你在 nums[i] 做两种选择，抢或者不抢，且抢了之后不能再抢相邻的位置，最后求最大收益。

这道题是让你在 days[i] 做三种选择，买一天的、七天的或三十天的，且买了之后，在这段时间内不用再买，最后求最小花费。

这题可以正向定义了（当然反向定义也可以），因为一天，七天或三十天，是确定的，方便状态转移，体会一下和「解决智力问题」的区别。

定义 dp[i] 表示 days[:i] 的最低消费，代码如下：

删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

题目有点点难理解，意思是选 nums[i] 就不能选 nums[i] ± 1。那其实就是打家劫舍问题。只需要将 nums[i] 按值的大小存起来作为 points。因为题目说 1 <= nums[i] <= 10000，所以我们可以用一个大小为 10001 的 points 数组来存储这个映射表。

要想得到最大点数，就要删除的少，那么既然选了 nums[i]，就把所有值等于它的全选了，所以 points 里存的实际上是数字和。

老鼠和奶酪

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：
如果第一只老鼠吃掉，则得分为 reward1[i] 。
如果第二只老鼠吃掉，则得分为 reward2[i] 。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大得分为多少。

翻译一下题目，就是 reward1 数组选 k 个，然后再加上 reward2 数组的剩下 n-k 个。

定义 dp[i][k] 表示前 i 个奶酪第一只恰好吃掉 k 块的最大得分。

但是内存爆炸了。上空间压缩大法：

时间又爆炸了，哈哈哈。

看下数据规模，n, k 都在 10^5 动态规划的复杂度是 O(n * k)，在 10^10 量级，确实很容易超时。

我们动态规划是无遗漏、无冗余地穷举了所有可能的解，依然超时，那就说明这道题大概率要用贪心的思路，找出一些巧妙的方法，避免穷举所有可行解来计算最优解。

我们尝试换个思路，这道题相当于就是让你在 reward1 中选 k 个元素，在 reward2 中选 n - k 个元素，使得元素之和最大。

想要让总的元素之和最大，可以让 reward1 中选择的 k 个元素尽可能「占便宜」，即选择 reward1[i] - reward2[i] 最大的 k 个元素。

那么有一个思路，就是把 reward1 和 reward2 的差值进行排序，然后选择前 k 个最大的差值作为从 reward1 中选择的元素，剩下的从 reward2 中选择。

优雅！

合并后数组中的最大元素

给你一个下标从 0 开始、由正整数组成的数组 nums 。
你可以在数组上执行下述操作任意次：
选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。
返回你可以从最终数组中获得的最大元素的值。

动态规划不行，但是贪心算法应该比较容易想到。

相当于要把所有非递减的相邻元素合并，肯定要先对靠后的元素进行合并，因为这样不会破坏已有的非递减关系，而且由于合并的关系，还可能创造新的非递减关系，使合并的非递减元素对尽可能多。

背包问题经典习题

背包问题是一类经典的动态规划问题，主要是在某个限制内，选择最优的元素组合。

其特点在于 dp 数组的定义方式，第一个维度的定义是「仅使用前 i 个物品」，之后的维度用来定义限制条件。

最后一块石头的重量 Ⅱ

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

这题的难点在于，如何看出它是一个背包问题。不过你看过「子集背包问题」，可能可以想到把这题转化成背包问题的方法。

任意两个石头会互相抵消，问你最后留下的石头重量，相当于是把 stones 数组分成两个子集，使得两个子集的重量差最小。

想要两个子集的重量差最小，那么两个子集的重量和应该尽可能接近 sum/2。那么问题就转化为了背包问题：

给定一个容量为 sum/2 的背包和若干石头 stones，请问这个背包能够装下的最大重量是多少？

这就是标准的 0-1 背包问题。定义 dp[i][j] 表示使用前 i 个石头，背包容量为 j 时，装下的最大重量。

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

标准的 0-1 背包问题，是在有限的背包容量下，计算物品的最大价值；这道题相当于背包有两个容量（0 和 1 的个数），然后计算最多能装多少个物品。

其中 0 和 1 的个数可以通过 strs.count() 计算。

执行操作可获得的最大总奖励 Ⅰ

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并标记下标 i。
以整数形式返回执行最优操作能够获得的最大总奖励。

首先看数据规模，数组长度是 2000 的规模，那么你的算法复杂度大概不能超过 O(N^2) 的级别，所以回溯这种暴力穷举算法肯定不考虑。

再看题目求的是最值，那么大概率是动态规划了，属于 0-1 背包的变体。

这个题的 rewardValues 就相当于是物品列表，rewardValues[i] 就相当于是第 i 个物品的价值，也是让你选择物品，使得物品的价值最大。

唯一的区别是，这道题并没有给一个固定的背包最大容量作为限制，而是把当前背包中的总价值 x 作为限制，你仅可以选择价值大于 x 的物品装进背包。

另外注意，这道题在进行状态转移之前需要对 rewardValues 进行排序。因为一般的背包问题给定了一个固定的背包容量，而这道题相当于你背包里的物品价值用来限制你的选择了，所以这个题要尽可能先装小价值的物品，如果你直接装一个大价值的物品进去，会导致后面的小价值物品装不进去，最终的结果偏小。

定义 dp[i][j] 表示前 i 个数能否得到奖励 j。和普通背包问题定义不同，因为背包没有确定的容量。

j 最大枚举到 2m-1，其中 m 是数组的最大值，证明如下：

如果最后一步选的数是 x，而 x<m，那么把 x 替换成 m 也符合要求，矛盾，所以最后一步选的一定是 m。在选 m 之前，元素和至多是 m−1，选了 m 之后，元素和至多是 2m−1。我们无法得到比 2m−1 更大的元素和。

下一题和这题描述一样，但是扩大了数据范围，上面的解会爆内存。上空间压缩大法，还是超时。只能祭出位运算大法了：

进一步地，把一维数组压缩成一个二进制数 f，其中二进制从低到高第 j 位为 1 表示 f[j]=true，为 0 表示 f[j]=false。转换后 ∨ 就是或运算（OR）了。

位运算可以去掉第二个循环。观察上述状态转移方程，其中，这相当于取 f 的低 v 位，再左移 v 位，然后与原来的 f 进行或运算。

小优化：代码实现时，可以先把 rewardValues 中的重复数字去掉再 DP，毕竟无法选两个一样的数。

小技巧：(1 << v) - 1 获得低 v 位。

优雅！

但是还可以用奇淫巧技继续优化。如果数组中包含 m-1，则答案为 2m-1；如果有两个不同元素之和等于 m−1，也可以直接返回 2m−1。由于在随机数据下，几乎 100% 的概率有两数之和等于 m−1，所以在大多数情况下，本题就是一道「两数之和」。

动态规划经典习题 Ⅰ

列举一些经典的动态规划习题，帮助大家加深理解前面文章中讲到的知识点。

整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ，k 不是常量），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

简单动态规划，设 dp[n] 表示拆分 n 获得的最大乘积。选择拆或者不拆。由于对称性，j 只需要到 i//2。

可以通过数学推导获得一个 O(1) 的算法，证明就不写了，结论是：若拆分的数量 k 确定，则 各拆分数字相等时 ，乘积最大；将数字 n 尽可能以因子 3 等分时，乘积最大。

不同路径 Ⅱ

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

简单动态规划，设 dp[i][j] 表示到坐标 (i,j) 的路径数。

可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。

定义 dp[i][j] 表示前 i 个元素除以三余数为 j 的元素最大和。

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

dp[i][j] 表示从顶到下标 (i,j) 的最小路径和。

最大整除子集

给你一个由无重复正整数组成的集合 nums，请你找出并返回其中最大的整除子集 answer，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。

这题有点难，不好想。需要先排序，排序很重要，假设一个符合题目要求的子集 [1,2,4]，那么由于我排了序，如果想扩充这个集合，接下来我只要到一个能够整除 4 的数就行了，比如 8。我不用考虑前面的数字了，因为只要能整除最大的 4 就一定能整除别的。

这样一来，题目就变成了：寻找一个最长递增子序列，且要求每个元素都能够整除前面那个元素。

dp[i] 表示以 nums[i] 结尾的最长递增子序列。

copy() 函数用于复制列表，类似于 a[:]，浅拷贝。

最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的最长公共子数组长度。

动态规划经典习题 Ⅱ

交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。
两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。

题目巴拉巴拉说了一大堆，实则就是一个使用双指针技巧合并两个字符串的过程。

但本题跟普通的数组/链表双指针技巧不同的是，这里需要穷举所有情况。比如 s1[i], s2[j] 都能匹配 s3[k] 的时候，到底应该让谁来匹配，才能完全合并出 s3 呢？

回答这个问题很简单，我不知道让谁来，那就都来试一遍好了。

设 dp[i][j] 表示 s1[:i] 和 s2[:j] 是否可以交错拼成 s3[i+j]。

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

这道题和 53. 最大子数组和 有点像，那道题定义的 dp 数组是：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」，从而写出状态转移方程。

这道题可以采用类似的思路，但需要注意的是，在 53 题中，子数组 nums[0..i] 的最大元素和是由 nums[0..i-1] 的最大元素和推导出的，但本题变成子数组的乘积则不一定。

比如 nums[i] = -1，nums[0..i-1] 子数组的最大元素乘积为 10，那么我能不能说 nums[0..i] 的最大元素乘积为 max(-1, -1 * 10) = -1 呢？

其实不行，因为可能nums[0..i-1] 子数组的最小元素乘积为 -6，那么 nums[0..i] 的最大元素乘积应该为 max(-1, -1 * 10, -1 * -6) = 6`。

所以这道题和 53 题的最大区别在于，要同时维护「以 nums[i] 结尾的最大子数组」和「以 nums[i] 结尾的最小子数组」，以便适配 nums[i] 可能为负的情况。

最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

定义 dp[i][j] 表示以坐标 (i,j) 为右下角的只包含 1 的最大正方形。

注意状态转移方程，三个相邻的取最小值。dp[i-1][j] 控制最后一列为 1，dp[i][j-1] 控制最后一行为 1，dp[i-1][j-1] 控制剩下的左上角为 1，matrix[i][j] 控制右下角的一格为 1。

另外，只记录边长比较方便，最后再取面积。

矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

好难。

「记忆化 DFS」

将矩阵看成一个有向图，每个单元格对应图中的一个节点，如果相邻的两个单元格的值不相等，则在相邻的两个单元格之间存在一条从较小值指向较大值的有向边。问题转化成在有向图中寻找最长路径。

「拓扑排序」

动态规划的状态定义和转移方程很简单，但是边界条件以及按照什么顺序来转移比较复杂。

如果一个单元格的值比它的所有相邻单元格的值都要大，那么这个单元格对应的最长递增路径是 1，这就是边界条件。这个边界条件并不直观，而是需要根据矩阵中的每个单元格的值找到作为边界条件的单元格。

仍然使用方法一的思想，将矩阵看成一个有向图，计算每个单元格对应的出度，即有多少条边从该单元格出发。对于作为边界条件的单元格，该单元格的值比所有的相邻单元格的值都要大，因此作为边界条件的单元格的出度都是 0。

基于出度的概念，可以使用拓扑排序求解。从所有出度为 0 的单元格开始广度优先搜索，每一轮搜索都会遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为 0 的单元格加入下一层搜索。当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度。

规划兼职工作

你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

「先按照结束时间排序」

定义 dp[i] 表示前 i 个工作的最大报酬。

如果不选第 i 个工作，那么最大报酬就是 dp[i-1]；

如果选第 i 个工作，那么就找满足 endTime[j] ≤ startTime[i] 的最大的 j，最大报酬为 dp[j] + profit[i]。由于已经按照结束时间排序了，所以 j 可以二分查找计算。

算法小课堂：标准库二分的灵活运用

bisect和bisect_right返回大于x的第一个下标(相当于C++中的upper_bound)

bisect.bisect_left返回大于等于x的第一个下标(相当于C++中的lower_bound)。

在写二分题目时，经常会遇到形如「在有序数组中查询大于某个数的最小数」这类问题。具体来说有四类：

≥：在有序数组中查询大于或等于某个数的最小数；

>：在有序数组中查询大于某个数的最小数；

≤：在有序数组中查询小于或等于某个数的最大数；

<：在有序数组中查询小于某个数的最大数。

上面的一些编程语言用到了标准库中的二分，但这些二分在设计的时候，只提供了查询 ≥ 和 > 的功能，并没有提供查询 ≤ 和 < 的功能。

没有关系，稍微转换下就能解决。比如查询 > 得到了下标 i，那么 i−1 就是 ≤ 的结果了（假设数组为升序），同理 < 可以用 ≥ 算出来。

注：> 和 ≥ 也可以转换，对于整数来说，>x 等价于 ≥x+1。