从暴力递归到动态规划
中心思想
所有的动态规划都能写成递归 但是不是所有的递归都能写成动态规划
对于一个不知从何分析的问题，我们的思路就是运用自然智慧将问题分解成子问题，利用暴力递归先解决，然后再去思考能不能通过记忆化搜索、动态规划、滚动数组的方式进行进一步优化。
解题思路
共计有 5 种解题思路，分别是从左往右的尝试模型，空间位置依赖模型，范围尝试模型，样本对应模型，业务限制模型
这些模型能够覆盖大部分面试遇到的 dp 问题。利用这些模型解决问题，最重要的是知道如何分解子问题，以及清晰的分析出子问题的所有可能情况。
一般情况下，像范围尝试和样本对应模型，在对子问题做情况分解时，往往会出现情况重叠的现象。此时，如果问题只是问 min 或者 max，只要能保证不进入死循环，基本都是可以求出正确答案的。
然而，如果问题求解时不涉及到比较(比较可以覆盖重复情况，因为max和min在重复情况下不会被影响)，比如求解”多少种方法”，“多少种路径”，若在情况分解时需要将各个情况的结果进行相加或者相减等运算，务必要保证情况之间无重叠！
从左往右的尝试模型
该模型一般都属于简单的dp问题，通常考虑的是在[0...idx]上的子问题，并不断增加idx至最大长度来完成问题的分析。
Note
显然，
(i)子问题依赖的应该是i+1的子问题，输入的是process(0)
- 拿背包问题举例，从左往右考虑指的是从
0增加idx，只考虑第idx位的货物要还是不要（即从左往右考虑货物） - 然而，从左往右考虑不一定只处理当前
idx位置，这样的问题可能无法转化成 dp，而是采用记忆化搜索。
范围尝试模型
一般输入是一个字符串的样子，思路是在 [L.. R]的范围上尝试 (含 R)，根据两个端点的可能情况来讨论情况
典型问题
样本对应模型
一般该类型的问题可能需要两个输入样本，一个样本 (s1) 做行一个样本 (s2) 做列的样本来进行对应。
问题分解成两个样本当前的范围上的子问题，即在 s1[0..i] 和 s2[0..j] 上的子问题。此时，子问题的情况分解是通过讨论当前两个样本的最右侧边界的可能性。
Note
显然，
(i, j)子问题依赖的应该是i-1或者j-1的子问题，输入的是process(len(s1)-1, len(s2)-1)，和从左到右的模型是不一样的
典型问题
空间位置依赖模型
该类问题的题目中一般都有明确的”位置”，比如题目中涉及到马在象棋盘上行走，或者机器人在一条直线上左右走。
典型问题包括
业务限制模型
这类问题课程讲的不多，暂时没有什么总结
咖啡机问题没看，需要单调栈的先验知识：https://www.bilibili.com/video/BV1KY4y1q78y?p=4&t=5571.1
状态压缩
在改写动态规划时，一定要十万分确定空间位置依赖关系后，决定恰当的遍历方向。
- 依赖左和上时，可以压缩成一维的
- 依赖左上和上时，同样可以压缩成一维的，反着来
- 依赖左、左上、上时，可以压缩成一维的，需要依赖一个额外的临时变量，提前一步保存左上的值不被上一步的值更新
一般来说，上面的问题都是压缩成一维的行 dp。
但是当行数非常巨大，但是列不大时，上面的问题同样可以被压缩成一维的列 dp。问题的思路是一样的，只是顺序略有不同，相当于转了 90 度而已。
因此可以主要考虑行、列那个小优化成哪一个。
- 枚举型的填写格子的行为，推严格位置依赖可以找到更好的方法，但是一般需要画个图。