6.0 KiB
动态规划
暴力递归就是尝试，暴力递归是动态规划的基础，暴力递归加上合理的剪枝和缓存就是动态规划。
暴力递归的步骤
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件(base case，递归终止条件)
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
暴力递归的几个常见问题
1、汉诺塔问题
打印n层汉诺，塔从最左边移动到最右边的全部过程，每次只能移动一个圆盘，不能出现大盘叠在小盘上面的情况。可以分为3个步骤。
- 将1-> n-1 移动到中间
- 将n移动到右边
- 将1-> n-1移动到右边
2、打印一个字符串的全部子序列
依次考察每一个字符是否被选中，递归逻辑可以画成整颗二叉树。每次递归前移除当前字符，递归完以后恢复当前字符。
3、打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
同上，加上set去重
4、打印一个字符串的全部排列
使用index和index后面的字符交换位置，index递增达到递归目的，index=str.length为递归终止条件。
5、打印一个字符串的全部排列，要求不要出现重复的排列
加上visited数组去重，避免重复的字符进行交换。
6、反转栈，不能使用额外集合，只能使用递归函数
两个递归函数，reverse使用f函数拿到栈底元素，然后递归，将栈底元素压栈。利用局部变量保存栈底元素，系统函数调用栈保证所有元素逆序。f函数拿到栈底元素，并保证其他元素顺序不变。
暴力递归和动态规划的关系
- 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
- 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
- 但不是所有的暴力递归，都一定对应着动态规划
暴力递归的优化
- 有重复调用同一个子问题的解，这种递归可以优化
- 如果每一个子问题都是不同的解，无法优化也不用优化
解决一个问题，可能有很多尝试方法，可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式，一个问题可能有若干种动态规划的解法。
如何找到某个问题的动态规划方式？
1）设计暴力递归：重要原则+4种常见尝试模型 2）分析有没有重复解：列出调用过程的前几层就能发现是否有重复解 3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决 4）看看能否继续优化：套路解决
暴力递归过程的原则
1）每一个可变参数的类型，一定不要比int类型更加复杂 2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数 3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可 4）可变参数的个数，能少则少 5）面试中违反以上原则的概率很小
常见的4种尝试模型
- 从左往右的尝试模型
- 范围上的尝试模型
- 多样本位置全对应的尝试模型
- 寻找业务限制的尝试模型
暴力递归到动态规划的套路
- 你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
- 找到哪些参数的变化会影响返回值，对每一个列出变化范围
- 参数间的所有的组合数量，意味着表大小
- 记忆化搜索的方法就是傻缓存，非常容易得到
- 规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
- 对于有枚举行为的决策过程，进一步优化
动态规划的进一步优化
- 空间压缩
- 状态化简
- 四边形不等式
- 其他优化技巧
机器人问题
假设有排成一行的N个位置，记为1~N，N 一定大于或等于2。开始时机器人在其中的M位置上(M一定是 1~N 中的一个)，如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种？ 给定四个参数 N、M、K、P，返回方法数。
扑克问题
给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
背包问题
给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
数字和字符转化问题
规定1和A对应、2和B对应、3和C对应...26和Z对应。那么一个数字字符串比如"111”就可以转化为:"AAA"、"KA"和"AK"。给定一个只有数字字符组成的字符串str，返回有多少种转化结果？
剪裁贴纸
给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文。arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。返回需要至少多少张贴纸可以完成这个任务。 例子：str= "babac"，arr = {"ba","c","abcd"} ba + ba + c 3 abcd + abcd 2 abcd+ba 2 所以返回2
最长公共子串
给定两个字符串str1和str2，返回这两个字符串的最长公共子序列长度。 比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”。最长公共子序列是“123456”，所以返回长度6