# 參考鏈接 [算法-動態規劃 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)) ```