牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。[
过去的动态规划时间复杂度为O(N*aim*aim)
暴力递归优化为动态规划的过程：
- 实现暴力递归方法
- 在暴力搜索方法的函数中看看哪些参数可以代表递归过程。
- 找到代表递归过程的参数之后，记忆化搜索的方法非常容易实现。
- 通过分析优化搜索的依赖路径，进而实现动态规划。
- 根据记忆化搜索方法改出动态规划方法，进而看看是否能化简，如果能化简，还能实现时间复杂度更低的动态规划方法。
动态规划方法的关键点：
- 最优化原理，也就是最优子结构性质。这指的是一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简单来说就是一个最优化策略的子策略总是最优的，如果一个问题满足最优化原理，就称其具有最优子结构性质。
- 无后效性。指的是某种状态下决策的收益，只与状态和决策相关，与到达该状态的方式无关。
- 子问题的重叠性。动态规划将原来具有指数级时间复杂度的暴力搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。
案例一： 有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法？ [
](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042258.png) **案例二：** 给定一个矩阵，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字加起来就是路径和，返回所有的路径中最小的路径和。如果给定的m如大家看到的样子，路径1，3，1，0，6，1，0是所有路径中路径和最小的，所以返回12. 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 从左到右计算每行的位置，然后再从上到下计算每一行，到最后最右下角的值就是整个问题的答案了：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042259.png) **案例三：** 给定数组arr，返回arr的最长递增子序列长度。比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]，所以返回这个子序列的长度5. dp：子序列长度[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042260.png) 从arr[0]开始，依次算出dp：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042261.png) **案例四：** 给定两个字符串str1和str2，返回两个字符串的最长公共子序列。例如，str1=“1A2C3D4B56”，str2=“B1D23CA45B6A”，“123456”或者“12C4B6”都是最长公共子序列，返回哪一个都行。[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042262.png) **案例五：** 一个背包有一定的承重W，有N件物品，每件都有自己的价值，记录在数组V中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042263.png) **案例六：** 给定两个字符串str1和str2，再给定三个整数ic,dc,rc，分别代表插入，删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。 比如，str1=“abc”，str2=”adc”，ic=5，dc=3，rc=2。从“abc”编辑成“adc”把‘b’替换成‘d’是代价最小的，所以返回2。 再比如，str1=“abc”，str2=“adc”，ic=5，dc=3，rc=100。从“abc”编辑成“adc”，先删除‘b’，然后插入‘d’是代价最小的，所以返回8.[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042264.png) 最终结果返回dp最右下角的值：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042265.png)
](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042258-300x257.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042258.png) **案例二：** 给定一个矩阵，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字加起来就是路径和，返回所有的路径中最小的路径和。如果给定的m如大家看到的样子，路径1，3，1，0，6，1，0是所有路径中路径和最小的，所以返回12. 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 从左到右计算每行的位置，然后再从上到下计算每一行，到最后最右下角的值就是整个问题的答案了：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042259.png) **案例三：** 给定数组arr，返回arr的最长递增子序列长度。比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]，所以返回这个子序列的长度5. dp：子序列长度[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042260.png) 从arr[0]开始，依次算出dp：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042261.png) **案例四：** 给定两个字符串str1和str2，返回两个字符串的最长公共子序列。例如，str1=“1A2C3D4B56”，str2=“B1D23CA45B6A”，“123456”或者“12C4B6”都是最长公共子序列，返回哪一个都行。[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042262.png) **案例五：** 一个背包有一定的承重W，有N件物品，每件都有自己的价值，记录在数组V中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042263.png) **案例六：** 给定两个字符串str1和str2，再给定三个整数ic,dc,rc，分别代表插入，删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。 比如，str1=“abc”，str2=”adc”，ic=5，dc=3，rc=2。从“abc”编辑成“adc”把‘b’替换成‘d’是代价最小的，所以返回2。 再比如，str1=“abc”，str2=“adc”，ic=5，dc=3，rc=100。从“abc”编辑成“adc”，先删除‘b’，然后插入‘d’是代价最小的，所以返回8.[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042264.png) 最终结果返回dp最右下角的值：[
Last updated:
](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042252.png) 暴力搜索方法：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042253.png) 定义递归函数：int p1(arr,index,aim)，它的含义是如果用arr[index…N-1]这些面值的钱组成aim，返回总的方法数。[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042254.png) **记忆搜索方法：**[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042255.png) **动态规划方法：**[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042256.png) **记忆搜索与动态规划的联系：** 01.记忆化搜索方法就是某种形态的动态规划方法。 02.记忆化搜索方法不关心到达某一个递归过程的路径，只是单纯地对计算过的递归过程进行记录，避免重复的递归过程。 03.动态规划的方法是规定好每一个递归过程的计算顺序，依次进行计算，后面的计算过程严格依赖卡面的计算过程。 04.两者都是空间换时间的方法，也有枚举的过程，区别就在于动态规划规定计算顺序，而记忆搜索不用规定。 **什么是动态规划方法？** [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042257.png) "过去的动态规划时间复杂度为O(N*aim*aim)")