|
|
## <center>动态规划</center>
|
|
|
|
|
|
  暴力递归就是尝试，暴力递归是动态规划的基础，暴力递归加上合理的剪枝和缓存就是动态规划。
|
|
|
<br />
|
|
|
|
|
|
### 暴力递归的步骤
|
|
|
|
|
|
* 把问题转化为规模缩小了的同类问题的子问题
|
|
|
* 有明确的不需要继续进行递归的条件(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函数拿到栈底元素，并保证其他元素顺序不变。
|
|
|
<br />
|
|
|
<br />
|
|
|
|
|
|
### 暴力递归和动态规划的关系
|
|
|
|
|
|
* 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
|
|
|
* 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
|
|
|
* 但不是所有的暴力递归，都一定对应着动态规划
|
|
|
|
|
|
### 暴力递归的优化
|
|
|
|
|
|
* 有重复调用同一个子问题的解，这种递归可以优化
|
|
|
* 如果每一个子问题都是不同的解，无法优化也不用优化
|
|
|
|
|
|
  解决一个问题，可能有很多尝试方法，可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式，一个问题可能有若干种动态规划的解法。
|
|
|
|
|
|
### 如何找到某个问题的动态规划方式？
|
|
|
|
|
|
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
|
