如何從青蛙跳臺階開始來了解Dynamic Programming

這篇文章給大家介紹如何從青蛙跳臺階開始來了解Dynamic Programming，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

動態規劃(Dynamic Programming)，簡稱 DP  相信大家在日常的工作或者學習的過程中都遇到過這個詞，而且動態規劃也是面試過程中最喜歡被問到的題目，阿粉在經歷的不多的幾場面試中都被問到了，實在是苦不堪言，不過好在阿粉還是有學過的，一些簡單的套路阿粉還是懂的。下面就從一個很多人應該都不陌生的題目講起。

案例 1

問：一只青蛙一次可以跳上 1 級臺階，也可以跳上 2 級，求該青蛙跳上一個 n 級的臺階總共有多少種跳法?

思考

剛開始看到這個題目的時候可能沒什么思路，不過我們可以一點點的想下去，我們假設青蛙跳上一個 n 級的臺階總共有多少種跳法 f(n)種跳法，那當 n = 0  時，f(0) = 0，沒有臺階當然沒有跳法。n = 1，f(1) = 1;只有一個臺階的時候，只能跳 1 個;n = 2，f(2) =  2，當有兩個臺階的時候，可以有 2 種跳法，一個一個跳和一下跳 2  個，那如果我們有三個臺階的話，是不是將一個臺階和兩個臺階的總和加起來就可以了呢?所以我們就可以想到 f(3) = f(2) + f(1)，所以我們能推導出  f(n) = f(n - 1) + f(n - 2);

編碼

上面的分析可以想到，那么接下來我們就需要用代碼來實現了，對于需要使用到之前的記錄，我們可以考慮用一維數組來記錄，所以就有了下面的這段代碼。

public int dp(int n) {     if (n <= 0) {         return 0;     }     int[] dp = new int[n + 1];     dp[0] = 0;     dp[1] = 1;     dp[2] = 2;    // 之所以要從 3 開始，是因為 2 不符合下面的規則     for (int i = 3; i <= n; i++) {         dp[i] = dp[i - 1] + dp[i - 2];     }     return dp[n]; }

解釋下上面的代碼，首先我們創建了一個一維數組 dp，用于記錄每個臺階有的跳法，然后從索引三開始遍歷，運用公式f(n) = f(n - 1) + f(n -  2); 進行賦值，結果直接輸出 dp[n] 對應的數值即可。

分析

通過上面的案例，我們思考一下對于動態規劃的題目我們需要怎么做，我們一開始定義了 n 級臺階有 f(n)  種跳法，然后通過模擬的方式計算出f(0),f(1),f(2)，接著我們找到了 f(n) = f(n - 1) + f(n - 2);  的關系。按照這種思路我們可以總結出三個步驟，分別是

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 定義變量：把已知的和需要求解的，定義出變量，如上面的 n 和 f(n);

3. 尋找表達式：找到 f(n) 和 f(n - 1) 以及 f(n - 2)，等情況的表達式，如上面的 f(n) = f(n - 1) + f(n -  2)，這一步往往是最難的;

4. 尋找初始值：確保找到所有的臨界條件，如上面的 f(0) = 0, f(1) = 1, f(2) = 2;

上面的步驟是通用步驟，往往在第一步的時候我們設置的 f(n)  是一個數組，根據具體的場景可能是一維數組也有可能是二維數組，上面的例子我們定義的就是一維數組，而且往往我們需要求解什么就定義什么數組。

下面我們通過這種方式再看一道 LeetCode 的原題

案例 2

問：一個機器人位于一個 m x n 網格的左上角 (起始點在下圖中標記為“Start”  )。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角(在下圖中標記為“Finish”)。問總共有多少條不同的路徑?

img

根據上面的三個步驟，我們依次來解決，既然是 m x n 的網格，很顯然我們需要用二維數組來解決問題，所以我們

1. 定義 d[m][n] 表示在 m x n 網格上移到右下角需要的總步數;

2. 因為機器人只能向右和向下移動，所以到達下一個格子只能是從左邊或者上面，所以達到 m x n 的步數等于(m - 1) x n + m x (n -  1)，也就是 d[m][n] = d[m - 1][n] + d[m][n - 1];

3. 定義初始值d[0][n] = 1，d[n][0] = 1，也就是只有一行或者一列的時候只有一種方法，全部向下或者向右移動;

編碼

public int dp(int m, int n) {     if (m <=0 || n <= 0) {         return 0;     }     int[][] dp = new int[m][n];     //只有一列的時候     for (int i = 0; i < m; i++) {         d[i][0] = 1;     }     //只有一行的時候      for (int i = 0; i < n; i++) {         d[0][i] = 1;     }         for (int i = 1; i < m; i++) {         for (int j = 1; j < n; j++) {             d[i][j] = d[i][j - 1] + d[i - 1][j];         }     }     //數組的下標從 0 開始     return d[m - 1][n - 1]; }

通過上面的三個步驟，我們可以完美的解決問題，動態規劃的問題難點就在于找尋規律和初始值，有點時候如果我們找不到規律就沒辦法了，而且如果初始值找的不完全也會有問題，這個只能多多練習了。

總結

動規劃的題目在 LeetCode  上面有很多，大家可以根據上面提供的思路去多刷幾道題，慢慢就會有感覺了，刷完動態規劃的題目，相信對大家工作或者找工作肯定有很大的幫助。

關于如何從青蛙跳臺階開始來了解Dynamic Programming就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。