##
动态规划
  暴力递归就是尝试,暴力递归是动态规划的基础,暴力递归加上合理的剪枝和缓存就是动态规划。
### 暴力递归的步骤 * 把问题转化为规模缩小了的同类问题的子问题 * 有明确的不需要继续进行递归的条件(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