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

成都創(chuàng)新互聯(lián)公司主要從事成都網(wǎng)站設(shè)計、成都網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)錫林浩特,10余年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

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

案例 1

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

思考

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

編碼

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

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

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

分析

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

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è)置的 f(n)  是一個數(shù)組，根據(jù)具體的場景可能是一維數(shù)組也有可能是二維數(shù)組，上面的例子我們定義的就是一維數(shù)組，而且往往我們需要求解什么就定義什么數(shù)組。

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

案例 2

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

img

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

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

2. 因為機(jī)器人只能向右和向下移動，所以到達(dá)下一個格子只能是從左邊或者上面，所以達(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，也就是只有一行或者一列的時候只有一種方法，全部向下或者向右移動;

編碼

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];         }     }     //數(shù)組的下標(biāo)從 0 開始     return d[m - 1][n - 1]; }

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

總結(jié)

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

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

網(wǎng)頁標(biāo)題：如何從青蛙跳臺階開始來了解DynamicProgramming
網(wǎng)站網(wǎng)址：http://www.rwnh.cn/article12/pgsidc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、網(wǎng)頁設(shè)計公司、網(wǎng)站營銷、響應(yīng)式網(wǎng)站、建站公司、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)