动态规划 – 序列型
序列型动态规划
这类题目上来一定丢给你一个类似序列东西，比如说一个数列 ${a_n}$，一个字符串 $S$或者说是一排房子。总之就是给你一堆东西，它们显式或者隐式地存在一种从前先后的顺序。
对于这种类型的题目，阶段地划分就按照序列从前往后的位置顺序进行，考虑到了第 $i$ 个位置，那么就位于阶段 $i$，结下来要往阶段 $i+1$ 转移。状态设计的时候，也会将序列中的位置作为状态表示的一维。例如 $dp[i]$，而这一维一般来说可以表示这几种信息：
- 第 / 前 $i$ 个位置的答案
- 前 $i$ 个位置里，第 $i$ 个位置一定选择的答案
两种信息基本相同，仅仅是第二种信息：可以看作将第一条的 第 与 前 合并了。当然，如果题目复杂一些，状态表示中可能还需要扩展出一些维度表示其他的信息，这就需要具体题目具体分析了。简单来说，你先用 $dp[i]$ 这个状态表示暴力上，看看还有哪些信息表达不了，加进来继续上，直到能完全表示为止，再看看那些状态表示是可以合并 / 优化的。
状态计算的顺序，就严格按照阶段顺序，我们先计算 $dp[1][xxx]$，再计算 $dp[2][xxx]$，直到最后计算 $dp[n][xxx]$。
状态转移方程，大概是这种样子的：
这里，$aaa, bbb$ 是额外的状态表示，它们之间可能需要满足题目的某种要求，用要求集合 $C$ 来表示。
$\mathop{opt}$ 就是视题目而定的操作了，一般来说可能是个 $\min$ 或者 $\max$, $\sum_{ccc}^{ddd}$ 啥的。
$cost_{i}$ 就是转移到状态 $i$ 的代价了，当然他也有可能会和 $aaa, bbb, j$ 有关系，也是视题目而定。（这里，也体现了动态规划的灵活，随便改一下状态表示、状态转移，换个题面就是一个新的题目，我一天能出 1W 道！
获取状态转移方程的要点还是从题目中找出和状态间关系相关的只言片语，先分析清楚状态之间的关系，再尝试推出状态转移方程。
再讲两个小技巧：
如果使用递推时间代码，我建议让动态规划有效状态的下表从 1 开始，把下表 0 让给一步决策都没有做的初始状态。通常这样做，可以让边界处理简单不少。
主动转移与被动转移。一个状态主动找它可以转移到哪些状态与更新一个状态的时候寻找哪些状态可以更新它，不同题目两种方式代码复杂度不同。
总结一下子，就是写代码之前想一想代码好不好写，如果发现不太好写，可以再多花几分钟看看怎么实现比较简单。
该讲的讲完啦，我们来看些例题加深一下理解。
斐波那契数列
LeetCode 70. 爬楼梯，LeetCode 509. 斐波那契数
|
1 2 3 4 5 6 7 8 9 10 |
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 示例 2： 输入： 3 输出： 3 |
这个题目大家 肯定 都会，看到题目就能这题在求 Fib 数列。主要意在让大家体会序列型动态规划的特点与状态表示。
我们爬楼梯有一种从下往上的顺序，这里就有了序列。最基础的状态表示 $dp[i]$ 表示（到达）第 $i$ 级位置（台阶）的答案（方案数），推算一下可以发现状态表示基本上没什么问题了。
再看状态表示，从题目中的 每次你可以爬 1 或 2 个台阶 这句话，我们可以得到状态之间的关系：$dp[i] = dp[i – 1] + dp[i – 2]$，这就是转移方程了。
边界，也就是我们容易得到答案的那些初始状态：
- 上 0 级台阶（初始）有一种方案
- 上 1 级台阶有 1 种方案
序列型动态规划计算状态的顺序无需多言，就是按照序列从前向后的顺序即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int climbStairs(int n) { int dp[n + 1]; dp[1] = dp[0] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; } }; |
那这道题目来讲的另一个目的就是，说说使用记忆化搜索，回忆一下上一节给出的记忆化搜索的框架。
这个问题的搜索程序很容易就能写出，我们在加入记忆化的部分就可以了。
边界就是搜不下去的两种情况：
- 台阶数为负数，那么方案数应该为 0 （不符合实际）
- 台阶数为 0，方案数为 1（还没有动身）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int dp[1050]; int dfs(int n){ if (n == 0) return 1; if (n < 0) return 0; if (dp[n] != -1) return dp[n]; dp[n] = dfs(n - 1) + dfs(n - 2); return dp[n]; } int climbStairs(int n) { memset(dp, -1, sizeof(dp)); return dfs(n); } }; |
最大子序和
LeetCode 53. 最大子序（段？）和，HDU 1003 Max Sum
|
1 2 3 4 5 6 7 |
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 |
话不多说，这是一个序列，考虑一下子序列型动态规划。按照之前的套路，状态表示为 $dp[i]$ 应该表示以第 $i$ 个数字结尾的最大和（前 $i$ 个数字中，第 $i$ 个数字一定选择的答案）。
而这道题目中，状态间的关系是我们需要分析一下的。考虑 $dp[i]$ 与 $dp[i + 1]$，它们分别表示以第 $i$ 个数字结尾的最大和与第 $i + 1$ 个数字结尾的最大和。$dp[i + 1]$ 的答案应该有两种情况：
- arr[i + 1]：第 $i + 1$ 个数字一定选，如果 $dp[i] \leq 0$，那么第 $i + 1$ 个数字接上第 $i$ 个数字结尾的最大子段和，反而变小了，不如不接！
- arr[i + 1] + dp[i]：第 $i + 1$ 个数字一定选，如果 $dp[i] > 0$，那么第 $i + 1$ 个数字接上以第 $i$ 个数字结尾的最大子段和，可以更大！
分析清楚了这件事情，状态转移方程可以得到：$dp[i + 1] = \max(0, dp[i]) + arr[i + 1]$。
边界按照之前的套路，造一个初始状态 $dp[0] = 0$ 即可，计算顺序就是序列顺序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int dp[n + 1] = {0}; for (int i = 1; i <= n; i++) dp[i] = max(dp[i - 1], 0) + nums[i - 1]; int ans = dp[1]; for (int i = 2; i <= n; i++) ans = max(ans, dp[i]); return ans; } }; |
打家劫舍
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 1: 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2: 输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 |
这里是一排房子，也是一个类似序列的东西。考虑最朴素的状态表示 $dp[i]$ 表示偷了前 $i$ 个房子的最大收益非法获利（前 $i$ 个位置的答案）。
这时候就发现有问题了，相邻的房子不能同时偷，但是我们的状态表示没有办法直到最后一个房子偷没偷，这个时候两种办法：
- 状态表示增加一维 $dp[i][0/1]$ 表示偷了前 $i$ 个房子，最后一个是否偷了的最大非法获利
- 改变状态表示意义 $dp[i]$ 表示偷了前 $i$ 个房子，最后一个一定偷的最大非法获利
先看第一种状态表示的修改方式，即 $dp[i][0/1]$ 表示偷了前 $i$ 个房子，最后一个是否偷了的最大非法获利，那么状态转移可以很容易得到：
dp[i][1] = dp[i – 1][0] + arr[i],\\
dp[i][0] = \max(dp[i – 1][0], dp[i – 1][1]).
\end{cases}
即考虑第 $i$ 个房子的时候：偷它，前一个就不能偷；不偷它，前一个可偷可不偷。最终的答案为 $max(dp[n][0], dp[n][1])$，为什么？想想看状态表示的意义。
状态的数量为 $O(n)$ 个，状态后继决策数量 $O(1)$，时间复杂度 $O(n)$。
再看第二种状态表示的修改方式：$dp[i]$ 表示偷了前 $i$ 个房子，最后一个一定偷的最大非法获利，那么状态转移为：
即考虑第 $i$ 个房子的时候，它一定偷了，那么我们不能偷 $i – 1$ 房子，我们可以从偷前面的其他房子转移过来。最终答案为 $max{dp[i]}_{i=1}^n$。
状态的数量为 $O(n)$，状态后继决策数量 $O(n)$，时间复杂度 $O(n^2)$。
显然是，第一种修改方式好，因为使用了更优秀的时间复杂度！这里插播一个我之前忘记讲的东西，动态规划的 时间复杂度 = 状态数量 * 决策数量 * 转移代价。
讲这个题目呢，主要的目的就是，让大家感受一下状态表示不能直接使用最朴素的，如何将其修改成能用的，多种可行的情况，哪一种更加合适。
康康代码，当然代码就没啥意思了，代码实现的是第一种状态表示修改。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); int dp[n + 1][2] = {0}; for (int i = 1; i <= n; i++){ dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = dp[i - 1][0] + nums[i - 1]; } return max(dp[n][0], dp[n][1]); } }; |
Take Home Message
序列型动态规划：
- 状态 $dp[i][aaa]$
- 转移
dp[i][aaa] = \mathop{opt}_{j=1}^{i-1}\{dp[j][bbb]\} + cost_{i}，(i, aaa, j, bbb) \in C
- 按序列顺序算状态，转移方程从题目中状态关系出
动态规划时间复杂度：状态数量 * 决策数量 * 转移代价
两个代码实现小技巧：
- 添加一个不存在的初始位置 $?_0$
- 主动转移与被动转移
课后作业
LeetCode 213 打家劫舍 II：如果现在是一个环，怎么转换成序列模型？
LeetCode 403 青蛙过河：一排石头。题目中有哪些信息需要加入状态表示？
LeetCode 1147 段式回文：和例题三的改法二有点类似？
LeetCode 1235 规划兼职工作：这里的序列是什么？
LeetCode 1220. 统计元音字母序列的数目：序列上的计数问题，额外维护个什么？
HDU 1087 Super Jumping! Jumping! Jumping!：论主动转移与被动转移的实现复杂度
HDU 1024 Max Sum Plus Plus：最大字段和加强版，想想看状态表示中需要增加哪些额外的信息？
HDU 1257 最少拦截系统：分析一下题目，怎么转化为序列型DP
参考文章
西风萧瑟@HDU
LeetCode 动态规划题组
HzwerのOI & ACM 课件收集整理
原文链接：动态规划 - 序列型
WNJXYKの博客 版权所有，转载请注明出处。
坑神啊，公式又有乱码了哦OωO
好难呀