主要参考灵神的视频
记忆化搜索：递归搜索 + 保存中间计算结果，如何思考状态转移是重点
递归：1:1 翻译 DFS 为 DP
启发思路：选或者不选 / 选哪个
三步走 🔥
- 思考回溯怎么写：① 入参是什么；② 递归到哪里；③ 注意递归边界和入口
- 改成记忆化搜索
- 1:1 翻译成递推：① dfs 改成 dp 数组；② 递归改成循环；③ 递归边界对应 dp 数组的初始化
时间复杂度：状态个数 * 单个状态计算时间
回溯三问：:fire:
- 当前操作是什么？枚举第 i 个房子选或者不选（倒着思考）
- 子问题是什么？从前 i 个房子中得到的最大金额和
- 下一个子问题什么？
- 「选」：从前 i-2 个房子中的得到的最大金额和
- 「不选」：从前 i-1 个房子中得到的最大金额和
得到状态转移方程：dfs(i) = max(dfs(i-1), dfs(i-2) + nums[i])
去掉递归中的「递」只保留「归」的过程，直接改成 dp 转移方程
dp[i+2] = max(dp[i+1], dp[i] + nums[i])
可以使用两个变量滚动记录 dp，优化空间
| 题目 | 说明 | 题解 |
|---|---|---|
| 72. 编辑距离 | 根据 s[i] ?= t[j] 将操作转换成 dfs(i, j) 的状态转移，转递推注意边界 | 0x3F |
| 1143. 最长公共子序列 | 根据 s[i] ?= t[j] 考虑 s[i] 和 t[j] 选或者不选得出 dfs(i, j) 的转移，然后转成递推 🔥 | 0x3F |
| 1092. 最短公共超序列 | 类似于最长公共子序列，但是直接使用记忆化dfs会超时，需要优化 | 0x3F |
| 1223. 掷骰子模拟 | dfs(i+1, last, left) 表示剩余 i 次投掷机会，上一个投掷的值为 last 且剩余次数为 left 的次数 | 0x3F |
| 1255. 得分最高的单词集合 | 参考灵神的子集型回溯，选或不选的思想，注意恢复现场 🔥 | 0x3F |
| 1641. 统计字典序元音字符串的数目 | dfs(i, j) 表示当前选择了第 0 个到第 i 个字符，最后一个字符是 j 的方案数 | coder_ps |
LC.1255 的 回溯三问
-
当前操作是什么？
枚举 words[i] 选或不选，如果不选，那么得分不变；如果选，那么统计 words[i] 中的每个字母对应的分数之和，累加到得分 total 中
-
子问题是什么？
(i, total) 表示当前状态：从前 i 个单词中继续选择，当前得分为 total
-
完成操作后，下一个子问题是什么？
不选 words[i] 递归到 dfs(i-1, total)；选 words[i] 递归到 dfs(i-1, total+s)，s 表示 words[i] 的得分
有限制的从最后枚举 j
| 题目 | 说明 | 题解 |
|---|---|---|
| 1043. 分隔数组以得到最大和 | 枚举最后一段的子数组下标 j，dfs(i) 表示 arr[0...i] 做分隔变换得到的最大元素和 | 0x3F |
| 1105. 填充书架 | dfs(i) 表示摆放 books[0...i] 可以做到的最小高度，枚举最后一层可以放置的书 | 通过 |
| 1335. 工作计划的最低难度 | dfs(i, j) 表示 j 天完成 job[0...i] 的最小难度，有限制的枚举最后一个天的工作 job[k...i] 取最大值 mx | 通过 |
| 1416. 恢复数组 | dfs(i) 表示 s[0...i] 字符串分割成数组的方案数，枚举末尾段字符子串 t 可能得分割方式，不能含有前导 0 并且不能超过 k | 通过 |
思考
这种题比较困难的就是找递推关系，根据题目意思从 i = 0 或者 i = n-1 开始找递推关系 dfs(i)，很多题目从后往前也就是 i = n-1 开始递推比较简单入手，然后再根据限制条件得到具体的 dfs(j) ，注意边界条件的返回值，写一个记忆化搜索，然后再到具体的递推
说白还是要多联系，很多题拿到之后没有题感也是很难找到递推的，比如 LC1043/LC1105 拿到题还不知道从最后一段可能的情况开始枚举也是比较难思考的