【演算法】動態規劃四步走
- 2020 年 3 月 12 日
- 筆記
動態規劃
動態規劃(dynamic programming)：它是把研究的問題分成若干個階段，且在每一個階段都要「動態地」做出決策，從而使整個階段都要取得最優效果。
理解：其實，無非就是利用歷史記錄，來避免我們的重複計算。
而這些歷史記錄，我們得需要一些變數來保存，一般是用一維數組或者多維數組來保存。
其實我挺好奇為什麼用動態規劃這個名字的，所以我花時間找了一下，如果大家想要知道這個名字的由來，可以去看看：動態規劃
動態規劃四步走
動態規劃四步走：
- 明確數組的含義：建立數組，明確數組元素的含義；
-
製作歷史記錄表：根據數組建表，填入初始值，利用遞推關係式寫程式推出其他空表項。
注意：這個是為我們通過初始值和遞推關係式寫出程式提供可視化條件以及思路，把抽象的東西可視化了，時時刻刻都知道自己要幹嘛。
當然，如果腦子裡有思路可以忽略。。 -
尋找數組初始值：尋找數組元素初始值；
注意：這個初始值要特別的給出一個出口，因為它們不是被遞推出來的。
-
找出遞推關係式：找出數組元素遞推關係式。
注意：可以從 dp[i] = ? 這一數學公式開始推想。
明確數組的含義
第一步：定義數組元素的含義。
上面說了，我們會用一個數組，來保存歷史記錄，假設用一維數組 dp[]吧。這個時候有一個非常非常重要的點，就是規定你這個數組元素的含義，即 你的 dp[i] 是代表什麼意思？
那麼下面我來舉個例子吧！
問題描述：一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法。
首先，拿到這個題，我們需要判斷用什麼方法，要跳上n級的台階，我們可能需要用到前幾級台階的數據，即 歷史記錄，所以我們可以用動態規劃。
然後依據上面我說的第一步，建立數組 dp[] ，那麼順理成章我們的 dp[i] 應該規定含義為：跳上一個i級的台階總共有dp[i]種解法。
那麼，求解dp[n]就是我們的任務。
製作歷史記錄表
- 根據數組，製表，確定一維表、二維表；
- 填入初始值；
-
根據遞推關係式，寫程式推出剩餘的空表項。
注意：這裡一維表比較簡單可能體現不出它的作用，到二維表它就能很方便的將數據可視化了。
此題，由於明確了數組的含義，我們可以確定是一張一維表。
歷史記錄表：
| 數組dp | 1 | 2 | 3 | … | n |
|---|---|---|---|---|---|
| 值 |
尋找數組初始值
第二步：找出初始值。
利用我們學過數學歸納法，我們可以知道如果要進行遞推，我們需要一個初始值來推出結果值，也就是我們常說的第一張多米諾骨牌。
本題的初始值很容易我們就找出來了，
- 當 n = 1 時，即 只有一級台階，那麼我們的青蛙只用跳一級就可以了，只有一種跳法，dp[1] = 1；
- 當 n = 2 時，即 有兩級台階，我們的青蛙有兩種選擇，一級一級的跳 和 一次跳兩級，dp[2] = 2；
- 當 n = 3 時，即 有三級台階，我們的青蛙跳一級 + dp[2]，或 跳兩級 + dp[1]，這時候我們就反應過來了，需要進行下一步找出 n 的遞推關係式。
歷史記錄表：
| 數組dp | 1 | 2 | 3 | … | n |
|---|---|---|---|---|---|
| 值 | 1 | 2 |
找出遞推關係式
第三步：找出數組元素之間的關係式。
動態規劃有一點類似於數學歸納法的，當我們要計算 dp[n] 時，是可以利用 dp[1]……dp[n-2]、dp[n-1] ，來推出 dp[n] 的，也就是可以利用歷史數據來推出新的元素值，所以我們要找出數組元素之間的關係式，例如， dp[i] = dp[i-1] + dp[i-2] ，這個就是它們的遞推關係式了。而這一步，也是最難的一步，後面我會講幾種類型的題來說。
當 n = i 時，即 有 i 級台階，我們的青蛙最後究竟怎麼樣到達的這第 i 級台階呢？
因為青蛙的彈跳力有限，只能一次跳一級或者兩級，所以我們有兩種方式可以到達最後的這第 i 級：
- 從 i-1 處跳一級
- 從 i-2 處跳兩級
所以，我們只需要把青蛙跳上 i-1 級台階 和 i-2 級台階的跳法加起來，我們就可以得到到達第 i 級的跳法（i≥3），即
[dp[i] = dp[i-1] + dp[i-2], (i≥3)]
這樣我們知道了初始值dp[1]、dp[2]，可以從dp[3]開始遞推出4、5、6、…、n。
歷史記錄表：
| 數組dp | 1 | 2 | 3 | … | n |
|---|---|---|---|---|---|
| 值 | 1 | 2 | 3 | … |
用程式循環得出後面的空表項。
你看有了初始值，以及數組元素之間的關係式，那麼我們就可以像數學歸納法那樣遞推得到dp[n]的值了，而dp[n]的含義是由你來定義的，你想求什麼，就定義它是什麼，這樣，這道題也就解出來了。
答案：
// 青蛙跳台階 int f(int n) { // 特別給初始值的出口 if(n <= 2) return n; // 創建數組保存歷史數據 int[] dp = new int[n+1]; // 給出初始值 dp[1] = 1; dp[2] = 2; // 通過遞推關係式來計算出 dp[n] for(int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } // 把最終結果返回 return dp[n]; }實例
超級青蛙跳台階
一個台階總共有 n 級，超級青蛙有能力一次跳到 n 階台階，也可以一次跳 n-1 階台階，也可以跳 n-2 階台階……也可以跳 1 階台階。
問超級青蛙跳到 n 層台階有多少種跳法？（n<=50）
例如：
輸入台階數：3
輸出種類數：4
解釋：4 種跳法分別是(1,1,1),(1,2),(2,1),(3)
答案：
這裡我是運用了「數學」來得出式子的，為了告訴大家不要拘泥於程式，數學也是一個很有用的工具。
用 Fib(n) 表示超級青蛙?跳上 n 階台階的跳法數。
如果按照定義，Fib(0)肯定需要為 0，否則沒有意義。我們設定 Fib(0) = 1；n = 0 是特殊情況，通過下面的分析會知道，令 Fib(0) = 1 很有好處。
PS：Fib(0)等於幾都不影響我們解題，但是會影響我們下面的分析理解。
-
當 n = 1 時， 只有一種跳法，即 1 階跳：(Fib(1) = 1);
-
當 n = 2 時， 有兩種跳的方式，一階跳和二階跳：(Fib(2) = 2);
到這裡為止，和普通跳台階是一樣的。 -
當 n = 3 時，有三種跳的方式，第一次跳出一階後，對應 Fib(3-1) 種跳法； 第一次跳出二階後，對應 Fib(3-2)種跳法；第一次跳出三階後，只有這一種跳法。
[Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4] -
當 n = 4 時，有四種方式：第一次跳出一階，對應 Fib(4-1)種跳法；第一次跳出二階，對應Fib(4-2)種跳法；第一次跳出三階，對應 Fib(4-3)種跳法；第一次跳出四階，只有一種跳法。
[Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4)] -
當 n = n 時，共有 n 種跳的方式：
第一次跳出一階後，後面還有 Fib(n-1)中跳法；
…
…
…
第一次跳出 n 階後，後面還有 Fib(n-n)中跳法。
[Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+…+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+…+Fib(n-1)]
通過上述分析，我們就得到了數列通項公式：
[Fib(n) = Fib(0)+Fib(1)+Fib(2)+…+ Fib(n-2) + Fib(n-1)]
因此，有 [Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+…+Fib(n-2)]
兩式相減得：[Fib(n)-Fib(n-1) = Fib(n-1)] [Fib(n) = 2*Fib(n-1), n >= 3]
這就是我們需要的遞推公式：[Fib(n) = 2*Fib(n-1), n >= 3]
public class SY1 { //自底向上的動態規劃 超級青蛙 N 階跳 static long solution(int number) { //題目保證 number 最大為 50 long[] Counter=new long[51]; Counter[0] = 1; Counter[1] = 1; Counter[2] = 2; int calculatedIndex = 2; if(number <= calculatedIndex) return Counter[number]; if(number > 50) //防止下標越界 number = 50; for(int i = calculatedIndex + 1; i <= number; i++) Counter[i] = 2 * Counter[i - 1]; calculatedIndex = number; return Counter[number]; } public static void main(String[] args) { Scanner cin = new Scanner(System.in); System.out.print(solution(cin.nextInt())); } }程式運行結果：
不同路徑
一個機器人位於一個 m x n 網格的左上角（起始點在下圖中標記為「Start」）。機器人試圖達到網格的右下角（在下圖中標記為「Finish」）。
- 機器人每次只能向下或者向右移動一步。
問總共有多少條不同的路徑？
例如，上圖是一個 3 x 7 的網格。有多少可能的路徑？
本題是 leetcode 的 62 號題：https://leetcode-cn.com/problems/unique-paths/
這裡為了讓大家能明白歷史記錄表的作用，我舉了一道二維表的題。
明確數組的含義
由題可知，我們的目的是從左上角到右下角一共有多少種路徑。
那我們就定義 dp[i][j]的含義為：當機器人從左上角走到 (i, j) 這個位置時，一共有 dp[i][j] 種路徑。
那麼 dp[m-1][n-1] 就是我們要找的答案了。
製作歷史記錄表
由於明確了數組的含義，我們可以知道這其實是一張二維表。
| 0 | 1 | 2 | … | m | |
|---|---|---|---|---|---|
| 0 | |||||
| 1 | |||||
| 2 | |||||
| … | |||||
| n |
尋找數組初始值
這時，看題目的要求限制：機器人每次只能向下或者向右移動一步。
所以我們從左上角開始，向下的那一列（即 第一列） 和 向右的那一行（即 第一行）上面所有的節點，都只有一條路徑到那。
因此，初始值如下：
- dp[0][0…n-1] = 1; // 第一行，機器人只能一直往右走
- dp[0…m-1][0] = 1; // 第一列，機器人只能一直往下走
歷史記錄表：
| 0 | 1 | 2 | … | m | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | … | 1 |
| 1 | 1 | ||||
| 2 | 1 | ||||
| … | … | ||||
| n | 1 |
找出遞推關係式
這是動態規劃四步走中最難的一步，我們從 dp[i][j] = ? 這一數學公式開始推想。
由於機器人只能向下走或者向右走，所以有兩種方式到達(i, j)：
- 一種是從 (i-1, j) 這個位置走一步到達
- 一種是從 (i, j-1) 這個位置走一步到達
所以我們可以知道，到達 (i, j) 的所有路徑為這兩種方式的和，可以得出遞推關係式：
dp[i][j] = dp[i-1, j] + dp[i, j-1]
歷史記錄表：
| 0 | 1 | 2 | … | m | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | … | 1 |
| 1 | 1 | 2 | 3 | ||
| 2 | 1 | 3 | 6 | ||
| … | … | ||||
| n | 1 |
我們可以利用此遞推關係式，寫出程式填完整個表項。
在下面程式碼中，我選擇的是逐行填入表格。
答案：
public static int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) { return 0; } int[][] dp = new int[m][n]; // 地圖 // 初始化 for(int i = 0; i < m; i++) { dp[i][0] = 1; } for(int i = 0; i < n; i++) { dp[0][i] = 1; } // 遞推 dp[m-1][n-1] for (int i = 1; i < m; i++) { // 逐行填寫空表格 for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }當程式碼敲完的那一刻，是不是就感覺這個二維表也太好看了吧。。。把抽象的東西可視化了，時時刻刻都知道自己要幹嘛。
