# 参考链接 [算法-动态规划 Dynamic Programming--从菜鸟到老鸟](https://blog.csdn.net/u013309870/article/details/75193592) [动态规划题解-CyC2018](https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md) # 原理篇 动态规划的核心是记录已经解决过的子问题的解。 ## 动态规划算法的两种形式 记录求解的方式有两种：① 自顶向下的备忘录法 ② 自底向上 以求斐波那契数列为例来介绍这两种方法： ```js Fibonacci (n) = 1; n = 0 Fibonacci (n) = 1; n = 1 Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2) ``` 1、自顶向下的备忘录方法 ```js function Fibonacci (n) { if (n <= 1) { // 从第 0 项开始，第 0 项为 0 return n } const Memo = new Array(n + 1) // JS 中初始化数组元素为 undefined for (let i = 0; i <= n; i++) { Memo[i] = -1 } return fib(n, Memo) function fib (n, Memo) { // 如果已经求出了 fib(n) 的值则直接返回，否则将求出的值保存在 Memo 备忘录 if (Memo[n] !== -1) return Memo[n] if (n <= 2) Memo[n] = 1 else Memo[n] = fib(n - 1, Memo) + fib(n - 2, Memo) return Memo[n] } } ```  备忘录法通过创建一个 n+1 大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面 fib(n) 的值计算出来了就不再计算，如果未计算出来，则计算出来后保存在 Memo 数组中，下次在调用 fib(n) 的时候就不会重新递归了。比如上面的递归树中在计算 fib(6) 的时候先计算 fib(5)，调用 fib(5) 算出了 fib(4) 后，fib(6) 再调用 fib(4) 就不会在递归 fib(4) 的子树了，因为 fib(4) 的值已经保存在 Memo[4] 中。 <span style="color: red">其与递归解法很相似，不同之处在于其通过备忘录的形式省去了重复计算某些子结点的这部分开销</span> 2、自底向上的动态规划 备忘录法还是利用了递归，上面算法不管怎样，计算 fib(6) 的时候最后还是要计算出 fib(1), fib(2), fib(3) ……那么何不先计算出 fib(1), fib(2), fib(3) ……呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。 ```js function Fibonacci (n) { if (n <= 1) return n const f = [] f[0] = 0 f[1] = 1 for (let i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2] } return f[n] } ``` ## 动态规划原理 什么样的问题可以采用动态规划解法？ 1、最优子结构 用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。 2、重叠子问题 如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。 ## 动态规划的经典模型 ### 线性模型 线性模型的是动态规划中最常用的模型，这里的线性指的是状态的排布是呈线性的。下面来看一个例题： 【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i 号小朋友过桥的时间为 T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。 【解答】： **我们先将所有人按花费时间递增进行排序** 假设前 i 个人过河花费的最少时间为 opt[i]，那么考虑前 i - 1 个人过河的情况，即河这边还有 1 个人，河那边有 i - 1 个人（已经有 i - 1 个人过河），并且这时候手电筒肯定在对岸，所以 opt[i] = opt[i - 1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第 i 个人一起过河) <br> 如果河这边还有两个人，一个是第 i 号，另外一个无所谓，河那边有 i - 2 个人，并且手电筒肯定在对岸，所以 opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第 i 个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题) 所以` opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2]} ` 来看一组数据：四个人过桥花费的时间分别为 1 2 5 10 具体步骤是这样的： 第一步：1 和 2 过去，花费时间 2，然后 1 回来（花费时间 1）； 第二歩：3 和 4 过去，花费时间 10，然后 2 回来（花费时间 2）； 第三步：1 和 2 过去，花费时间 2，总耗时 17。 ### 区间模型 区间模型的状态表示一般为 d\[i\]\[j\]，表示区间 \[i, j\] 上的最优解，然后通过状态转移计算出 \[i+1, j\] 或者 \[i, j+1\] 上的最优解，逐步扩大区间的范围，最终求得 \[1, len\] 的最优解。 【例题2】 给定一个长度为 n（n <= 1000）的字符串 A，求插入最少多少个字符使得它变成一个回文串。 【解答】 典型的区间模型，回文串拥有很明显的子结构特征，即当字符串 X 是一个回文串时，在 X 两边各添加一个字符 'a' 后，aXa 仍然是一个回文串，我们用 d[i][j] 来表示 A[i…j] 这个子串变成回文串所需要添加的最少的字符数，那么对于 A[i] == A[j] 的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点，当 i+1 > j-1 时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下 d[i+1][j-1] = 0）；当 A[i] != A[j] 时，我们将它变成更小的子问题求解，我们有两种决策： 1、在 A[j] 后面添加一个字符 A[i]； 2、在 A[i] 前面添加一个字符 A[j]； 根据两种决策列出状态转移方程为：`d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1`(每次状态转移，区间长度增加1) ### 背包模型 【例题3】有 N 种物品（每种物品 1 件）和一个容量为 V 的背包。放入第 i 种物品耗费的空间是 Ci，得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v] 表示前i种物品恰好放入一个容量为 v 的背包可以获得的最大价值。决策为第 i 个物品在前 i-1 个物品放置完毕后，是选择放还是不放，状态转移方程为： `f[i][v] = max{ f[i-1][v], f[i-1][v – Ci] +Wi }` # 刷题篇 ## 强盗抢劫 [198\. House Robber (Easy)](https://leetcode.com/problems/house-robber/description/) 题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。 定义 dp 数组用来存储最大的抢劫量，其中 dp\[i\] 表示抢到第 i 个住户时的最大抢劫量。 由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以 `dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])` ```js var rob = function(nums) { let pre2 = 0, pre1 = 0 for (let i = 0; i < nums.length; i++) { let cur = Math.max(pre2 + nums[i], pre1) pre2 = pre1 pre1 = cur } return pre1 }; ``` ## 强盗在环形街区抢劫 [213\. House Robber II (Medium)](https://leetcode.com/problems/house-robber-ii/description/) ```js var rob = function(nums) { if (nums === null || nums.length === 0) return 0 let n = nums.length if (n === 1) return nums[0] return Math.max(mrob(nums, 0, n - 2), mrob(nums, 1, n - 1)) }; function mrob(nums, first, last) { let pre2 = 0, pre1 = 0 for (let i = first; i <= last; i++) { let cur = Math.max(pre1, pre2 + nums[i]) pre2 = pre1 pre1 = cur } return pre1 } ``` ## 矩阵的最小路径和 [64\. Minimum Path Sum (Medium)](https://leetcode.com/problems/minimum-path-sum/description/) ```txt Input: [   [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. ``` 题目描述：求从矩阵的左上角到右下角的最小路径和，每次只能向右和向下移动。 ```js /** * @param {number[][]} grid * @return {number} */ var minPathSum = function(grid) { let row = grid.length let col = grid[0].length const dp = [] for (let i = 0; i < row; i++) { dp[i] = [] } for (let i = 0; i < row; i++) { dp[i][0] = i === 0 ? grid[0][0] : dp[i - 1][0] + grid[i][0] } for (let j = 1; j < col; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j] } for (let i = 1; i < row; i++) { for (let j = 1; j < col; j++) { dp[i][j] = Math.min(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j]) } } return dp[row - 1][col - 1] }; ``` ## 数组中等差递增子区间的个数 [413\. Arithmetic Slices (Medium)](https://leetcode.com/problems/arithmetic-slices/description/) ```txt A = [0, 1, 2, 3, 4] return: 6, for 3 arithmetic slices in A: [0, 1, 2], [1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3, 4], [ 1, 2, 3, 4], [2, 3, 4] ``` 解题思路：dp\[i\] 表示以 A\[i\] 为结尾的等差递增子区间的个数。 当 A\[i\] - A\[i-1\] == A\[i-1\] - A\[i-2\]，那么 \[A\[i-2\], A\[i-1\], A\[i\]\] 构成一个等差递增子区间。而且在以 A\[i-1\] 为结尾的递增子区间的后面再加上一个 A\[i\]，一样可以构成新的递增子区间。 ```txt dp[2] = 1 [0, 1, 2] dp[3] = dp[2] + 1 = 2 [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3 [1, 2, 3] // 新的递增子区间 dp[4] = dp[3] + 1 = 3 [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4 [1, 2, 3, 4], // [1, 2, 3] 之后加一个 4 [2, 3, 4] // 新的递增子区间 ``` 综上，在 A\[i\] - A\[i-1\] == A\[i-1\] - A\[i-2\] 时，dp\[i\] = dp\[i-1\] + 1。 因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回 dp 数组累加的结果。 ```js /** * @param {number[]} A * @return {number} */ var numberOfArithmeticSlices = function(A) { if (A === null || A.length === 0) { return 0 } let n = A.length let dp = [] dp[0] = dp[1] = 0 let total = 0 for (let i = 2; i < n; i++) { dp[i] = 0 if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) { dp[i] = dp[i - 1] + 1 total += dp[i] } } return total }; ``` ## 字符串最小变换次数 [NowCoder](https://www.nowcoder.com/practice/2561ad26e8804cf8801926f03708ef03?tpId=98&tqId=32983&tPage=8&rp=8&ru=/ta/2019test&qru=/ta/2019test/question-ranking) 给定两个字符串，已知可以使用三种方式进行变换 1\. 插入一个字符 2\. 删除一个字符 3\. 更改一个字符 请设计一个算法，找到两个字符串之间的经历几次最小变换，可以字符串 1 转换成字符串 详细解析：[https://blog.csdn.net/sinat\_35261315/article/details/78678961](https://blog.csdn.net/sinat_35261315/article/details/78678961) ```js let s1 = readline() let s2 = readline() // 定义dp[i][j]表示将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]所需要的最小操作次数。 function getMinTransTimes (s1, s2) { let len1 = s1.length + 1, len2 = s2.length + 1 let dp = [] for (let i = 0; i < len1; i++) { dp[i] = [] dp[i][0] = i } for (let i = 0; i < len2; i++) { dp[0][i] = i } for (let i = 1; i < len1; i++) { for (let j = 1; j < len2; j++) { // 如果word1[i - 1] == word2[j - 1]， // 那么对于将字符word1[i - 1]转换到word2[j - 1]是不需要任何操作的 if (s1[i - 1] === s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { /* 如果word1[i - 1] != word2[j - 1]，此时有三种方式可以将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1] 1.将word1[i - 1]替换成word2[j - 1]，此时dp[i][j] = 1 + dp[i - 1][j - 1] 2.将word1[i - 1]删掉，此时dp[i][j] = 1 + dp[i - 1][j] 3.在word1的i - 1位置插入字符word2[ j - 1]，此时dp[i][j] = 1 + dp[i][j - 1] */ dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1) dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1) } } } return dp[len1 - 1][len2 - 1] } print(getMinTransTimes(s1, s2)) ```