如何從青蛙跳臺(tái)階開始來(lái)了解Dynamic Programming

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

動(dòng)態(tài)規(guī)劃(Dynamic Programming)，簡(jiǎn)稱 DP  相信大家在日常的工作或者學(xué)習(xí)的過(guò)程中都遇到過(guò)這個(gè)詞，而且動(dòng)態(tài)規(guī)劃也是面試過(guò)程中最喜歡被問(wèn)到的題目，阿粉在經(jīng)歷的不多的幾場(chǎng)面試中都被問(wèn)到了，實(shí)在是苦不堪言，不過(guò)好在阿粉還是有學(xué)過(guò)的，一些簡(jiǎn)單的套路阿粉還是懂的。下面就從一個(gè)很多人應(yīng)該都不陌生的題目講起。

案例 1

問(wèn)：一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)，求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法?

思考

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

編碼

上面的分析可以想到，那么接下來(lái)我們就需要用代碼來(lái)實(shí)現(xiàn)了，對(duì)于需要使用到之前的記錄，我們可以考慮用一維數(shù)組來(lái)記錄，所以就有了下面的這段代碼。

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 開始，是因?yàn)?nbsp;2 不符合下面的規(guī)則     for (int i = 3; i <= n; i++) {         dp[i] = dp[i - 1] + dp[i - 2];     }     return dp[n]; }

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

分析

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

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

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

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

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

上面的步驟是通用步驟，往往在第一步的時(shí)候我們?cè)O(shè)置的 f(n)  是一個(gè)數(shù)組，根據(jù)具體的場(chǎng)景可能是一維數(shù)組也有可能是二維數(shù)組，上面的例子我們定義的就是一維數(shù)組，而且往往我們需要求解什么就定義什么數(shù)組。

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

案例 2

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

img

根據(jù)上面的三個(gè)步驟，我們依次來(lái)解決，既然是 m x n 的網(wǎng)格，很顯然我們需要用二維數(shù)組來(lái)解決問(wèn)題，所以我們

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

2. 因?yàn)闄C(jī)器人只能向右和向下移動(dòng)，所以到達(dá)下一個(gè)格子只能是從左邊或者上面，所以達(dá)到 m x n 的步數(shù)等于(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，也就是只有一行或者一列的時(shí)候只有一種方法，全部向下或者向右移動(dòng);

編碼

public int dp(int m, int n) {     if (m <=0 || n <= 0) {         return 0;     }     int[][] dp = new int[m][n];     //只有一列的時(shí)候     for (int i = 0; i < m; i++) {         d[i][0] = 1;     }     //只有一行的時(shí)候      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];         }     }     //數(shù)組的下標(biāo)從 0 開始     return d[m - 1][n - 1]; }

通過(guò)上面的三個(gè)步驟，我們可以完美的解決問(wèn)題，動(dòng)態(tài)規(guī)劃的問(wèn)題難點(diǎn)就在于找尋規(guī)律和初始值，有點(diǎn)時(shí)候如果我們找不到規(guī)律就沒辦法了，而且如果初始值找的不完全也會(huì)有問(wèn)題，這個(gè)只能多多練習(xí)了。

總結(jié)

動(dòng)規(guī)劃的題目在 LeetCode  上面有很多，大家可以根據(jù)上面提供的思路去多刷幾道題，慢慢就會(huì)有感覺了，刷完動(dòng)態(tài)規(guī)劃的題目，相信對(duì)大家工作或者找工作肯定有很大的幫助。

關(guān)于如何從青蛙跳臺(tái)階開始來(lái)了解Dynamic Programming就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。