什么样的暴力递归可以继续优化
- 有重复调用一个子问题的解，这类递归可以优化
- 如果每一个子问题都是不同解，无法优化也不用优化
暴力递归和动态规划的关系
- 某一个暴力递归有解的重复调用，即可以把这个暴力递归优化为动态规划
- 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
- 不是所有的暴力递归都一定对应着动态规划
暴力递归过程的设计原则（面试）
- 每一个可变参数的类型不要比 int 类型更加复杂
- 原则1 可以违反，可以让类型突破到一维线性结构，但必须是单一可变参数
- 如果原则1 被违反，但是不违反原则2，只需要做到记忆化搜索即可
- 可变参数的个数应能少则少
常见的4种尝试模型
- 从左往右的尝试模型
- 范围上的尝试模型
- 多样本位置全对应的尝试模型
- 寻找业务限制的尝试模型
如何找到某个问题的动态规划方式
- 设计暴力递归：重要原则+4种常见尝试模型（重要）
- 分析有没有重复解：套路解决
- 用记忆化搜索：用严格表结构实现动态规划，套路解决
- 看看能够继续优化：套路解决
暴力递归到动态规划的套路
- 已经有个了一个不违反原则的暴力递归，并且存在解的重复调用
- 找到哪些参数的变化会影响返回值，对每一个列出变化范围
- 参数间的所有组合数量意味着表的大小
- 总能改出记忆化搜索的方法，也就是傻缓存，非常容易得到
- 规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
- 对于有枚举行为的决策过程，进一步优化
动态规划的进一步优化
- 空间压缩
- 状态化简
- 四边形不等式
- 其他优化技巧