面试中设计暴力递归过程的原则
大约 4 分钟
面试中设计暴力递归过程的原则
暴力递归和动态规划的关系
- 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
- 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归，但不是所有的暴力递归，都一定对应着动态规划
原则
- 每一个可变参数的类型，一定不要比int类型更加复杂
- 原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参
- 如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可
- 可变参数的个数，能少则少
- 递归函数的可变参数不能是数组类型，一个可变参数就是一维表，两个可变参数就是二维表。
如何找到某个问题的动态规划方式？
- 设计暴力递归：重要原则+4种常见尝试模型！重点！
- 从左往右的尝试模型
- 范围上的尝试模型
- 多样本位置全对应的尝试模型
- 寻找业务限制的尝试模型
- 分析有没有重复解：套路解决
- 用记忆化搜索->用严格表结构实现动态规划：套路解决
- 看看能否继续优化：套路解决
暴力递归到动态规划的套路
- 你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
- 找到哪些参数的变化会影响返回值，对每一个列出变化范围
- 参数间的所有的组合数量，意味着表大小
- 记忆化搜索的方法就是傻缓存，非常容易得到
- 规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
- 对于有枚举行为的决策过程，进一步优化
记住求解的方式有两种
- 自顶向下的备忘录法
- 自底向上。
在求解问题中,对于每一步决策,列出各种可能的局部解,再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一步都是最优解来保证全局是最优解。
如何分析有没有重复解
- 列出调用过程，可以只列出前几层
- 有没有重复解，一看便知
动态规划的进一步优化
- 空间压缩
- 状态化简
- 四边形不等式
- 其他优化技巧
滚动数组是DP中的一种编程思想。简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。起到优化空间，主要应用在递推或动态规划中。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。
知道了面试中设计暴力递归过程的原则，然后呢？一定要逼自己找到不违反原则情况下的暴力尝试！如果你找到的暴力尝试，不符合原则，马上舍弃！找新的！如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%！
暴力转成动态规划总结：
- 暴力递归的return值，dp也要进行赋值。
- 暴力的递归尝试改成从dp中取值。
- 递归参数是减，那么dp的for循环就是从小到大，从初始数据先写0也能看出来是从小到大循环
- 递归返回的参数是min。那么在递归中最上面min = Integer.MaxValue, 就需要给dp数组都赋值为此。而不是继续使用min
- 写递归方法时，判定停止条件可以是index == nums.length 也可以是index == nums.length - 1，这个停止条件适合那种小人移动问题，比如说一个m*n 数组最短路径，爬楼梯，打家劫舍；其余的都用index == nums.length
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解