動態規劃快速入門
- 2019 年 10 月 3 日
- 筆記
更多內容，歡迎關注微信公眾號：全菜工程師小輝。公眾號回復關鍵詞，領取免費學習資料。
動態規劃演算法一直是面試手撕演算法中比較有挑戰的一種類型。很多的分配問題或者調度問題實際上都可能用動態規划進行解決。（當然，如果問題的規模較大，有時候會抽象模型使用動歸來解決，有時候則可以通過不斷迭代的概率演算法解決查找次優解）
所以，動歸很重要，至少演算法思想很重要。
什麼是動態規劃？
通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題。
最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。
重疊子問題：在用遞歸演算法自頂向下解問題時，每次產生的子問題並不總是新問題，有些子問題被反覆計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而後將其解保存在一個表格中，在以後儘可能多地利用這些子問題的解。
不理解不用怕，結合後面題目來理解這些概念。這些概念完全是已經會動歸的人來總結出來的，所以先理解動歸，然後再來看這些文縐縐的概括。
分治與動態規劃
共同點：
二者都要求原問題具有最優子結構性質，都是將原問題分而治之，分解成若干個規模較小（小到很容易解決）的子問題。然後將子問題的解合併，形成原問題的解。
不同點：
- 分治法將分解後的子問題看成相互獨立的，通過用遞歸來做。
- 動態規劃將分解後的子問題理解為相互間有聯繫，有重疊部分，需要記憶，通常用迭代來做。
動態規劃的步驟
問題建模
- 根據問題，找到【最優子結構】。把原問題從大化小的第一步，找到比當前問題要小一號的最好的結果，而一般情況下當前問題可以由最優子結構進行表示。
- 確定問題的【邊界】。根據上述的最優子結構，一步一步從大化小，最終可以得到最小的，可以一眼看出答案的最優子結構，也就是邊界。
-
通過上述兩步，通過分析最優子結構與最終問題之間的關係，我們可以得到【狀態轉移方程】。
問題求解的各個方法
暴力枚舉：
所有的動態規劃問題都可以通過多層嵌套循環遍歷所有的可能，將符合條件的個數統計起來。只是時間複雜度是指數級的，所以不推薦。
遞歸：
- 遞歸的時間複雜度是由遞歸層數和最優子結構的個數決定的。
- 在爬階梯問題，最少找零錢問題中，遞歸的時間複雜度和空間複雜度都比動歸方法的差，但是在國王與金礦的問題中，不同的數據規模，動歸方法的時間複雜度和空間複雜度不一定比遞歸的要好。所以具體問題具體分析。
上面提到的三個問題是動態規劃里很常見的題目，題目內容可以百度查看一下。篇幅原因，本文後邊只講解前兩道題
備忘錄演算法：
- 在階梯數N比較多的時候，遞歸演算法的缺點就顯露出來了：時間複雜度很高。如果畫出遞歸圖（像二叉樹一樣），會發現有很多很多重複的節點。然而傳統的遞歸演算法並不能識別節點是不是重複的，只要不到終止條件，它就會一直遞歸下去。
- 為了避免上述情況，使遞歸演算法能夠不重複遞歸，就把已經得到的節點都存起來，下次再遇到的時候，直接用存起來的結果就行了。這就是備忘錄演算法。
- 備忘錄演算法的時間複雜度和空間複雜度都得到了簡化。
動態規劃演算法：
- 上述的備忘錄演算法，儘管已經不錯了，但是依然還是從原問題，遍歷得到所有的最小子問題，空間複雜度是O(N)。
- 為了再次縮小空間複雜度，我們可以自底向上的構造遞歸問題，通過分析最優子結構與最終問題之間的關係，我們可以得到【狀態轉移方程】。
然後從最小的問題不斷往上迭代，即使一直迭代到最大的原問題，也是只依賴於前面的幾個最優子結構。這樣，空間複雜度就大大簡化。也就得到了動歸演算法演算法。
例題
例1: Climbing Stairs(爬樓梯問題)
leetcode原題：你正在爬一個有n個台階的樓梯，每次只能上1個或者2個台階，那麼到達頂端共有多少種不同的方法？
- 建立模型：
- 最終問題F(N)：假設從0到達第N個台階的方法共有F(N)個。
- 最優子結構F(N-1)，F(N-2)：到達N個台階，有兩種可能，第一種可能是從第 N-1 個台階上1個台階到達終點，第二種可能是從第 N-2 個台階上2個台階到達終點。
- 最優子結構與最終問題之間的關係：按照上述表達，那麼可以歸納出F(N) = F(N-1) + F(N-2) (n>=3)
- 邊界:F(1) = 1,F(2) = 2
- 問題求解：
- 遞歸：
class Solution { int climbStairs(int n) { if (n <= 2) { return n; } else { return climbStairs(n - 1) + climbStairs(n - 2); } } }遞歸的時間複雜度是由遞歸層數和最優子結構的個數決定的。這裡的階梯數是 N ，最優子結構個數是2。如果想像成一個二叉樹，那麼就可以認為是一個高度為N-1，節點個數接近2的N-1次方的樹，因此此方法的時間複雜度可以近似的看作是O(2N) 。
- 備忘錄演算法：
這裡我們想到了把重複的參數存儲起來，下次遞歸遇到時就直接返回該參數的結果，也就是備忘錄演算法了，最簡單的備忘錄就是哈希表。
class Solution { private Map<Integer, Integer> map = new HashMap<>(); int climbStairs(int n) { if (n <= 2) { return n; } else if (map.containsKey(n)) { return map.get(n); } else { int value = climbStairs(n - 1) + climbStairs(n - 2); map.put(n, value); return value; } } }- 動態規劃：
之前都是自頂向下的求解，考慮一下自底向上的求解過程。從F(1)和F(2)邊界條件求，可知F(3) = F(1)+F(2)。不斷向上，可知F(N)只依賴於前兩個狀態F(N-1)和F(N-2)。於是我們只需要保留前兩個狀態，就可以求得F(N)。相比於備忘錄演算法，我們再一次簡化了空間複雜度。
class Solution { int climbStairs(int n) { if (n <= 2) { return n; } // 邊界條件 int a = 1; int b = 2; int result = 0; // 最優子結構與最終問題之間的關係 for (int i = 3; i <= n; i++) { result = a + b; a = b; b = result; } return result; } }空間複雜度O(1), 時間複雜度O(N)
例2: Making change using the fewest coins(最少找零錢問題)
Google面試題：假設你是一家自動售貨機製造商的程式設計師。你的公司正設法在每一筆交易 找零時都能提供最少數目的硬幣以便工作能更加簡單。已知硬幣有四種（1美分，5美分，10美分，25美分）。假設一個顧客投了1美元來購買37美分的物品 ，你用來找零的硬幣的最小數量是多少？
- 建立模型：
- 最優子結構：回想找到最優子結構的方法，就是往後退一步，能夠得到的最好的結果。這裡有四個選擇，1 + mincoins(63-1)，1 + mincoins(63-5)，1 + mincoins(63-10) 或者 1 + mincoins(63-25)，這四個選擇可以認為是63的最優子結構。
- 狀態轉移方程：按照上述的最優子結構，mincoins(63)也就等於上述四個最優子結構的最小值。
- 邊界: 當需要找零的面額正好等於手中單枚硬幣的金額時，返回1即可。
- 問題求解：
- 遞歸：
class Solution { Set<Integer> coinSet = new HashSet<Integer>() { { add(1); add(5); add(10); add(25); } }; int getFewestCoins(int n) { if (n < 1) { return 0; } if (coinSet.contains(n)) { return 1; } int minCoins = n; int numCoins = Integer.MAX_VALUE; for (int coin : coinSet) { if (n >= coin) { // 如果要計算的n小於單個硬幣金額，則不能出現在狀態轉移方程中 numCoins = 1 + getFewestCoins(n - coin); } // 更新最小值 if (numCoins < minCoins) { minCoins = numCoins; } } return minCoins; } }-
備忘錄演算法：
就是將遞歸里計算的中間變數都保存在一個哈希表，程式碼略。 -
動態規劃：
自底向上，從找零數等於1開始往上迭代，參考最優子結構，記錄下來最少硬幣數。一直迭代到實際要求。
class Solution { Set<Integer> coinSet = new HashSet<Integer>() { { add(1); add(5); add(10); add(25); } }; int getFewestCoins(int n) { int[] list = new int[n + 1]; List<Integer> subCal = new ArrayList<>(); for (int i = 0; i <= n; i++) { // 邊界 if (i <= 1) { list[i] = i; continue; } for (int cent : coinSet) { if (i >= cent) { subCal.add(list[i - cent] + 1); } } list[i] = Collections.min(subCal); subCal.clear(); } return list[n]; } }更多內容，歡迎關注微信公眾號：全菜工程師小輝。公眾號回復關鍵詞，領取免費學習資料。
