建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「Java極客技術(shù)」，作者鴨血粉絲。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java極客技術(shù)公眾號(hào)。
成都創(chuàng)新互聯(lián)公司技術(shù)團(tuán)隊(duì)十多年來(lái)致力于為客戶提供網(wǎng)站建設(shè)、成都做網(wǎng)站、成都品牌網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷推廣、搜索引擎SEO優(yōu)化等服務(wù)。經(jīng)過(guò)多年發(fā)展，公司擁有經(jīng)驗(yàn)豐富的技術(shù)團(tuán)隊(duì)，先后服務(wù)、推廣了上千網(wǎng)站，包括各類中小企業(yè)、企事單位、高校等機(jī)構(gòu)單位。
Hello 大家好，我是阿粉，動(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)階總共有多少種跳法?
思考
剛開(kāi)始看到這個(gè)題目的時(shí)候可能沒(méi)什么思路，不過(guò)我們可以一點(diǎn)點(diǎn)的想下去，我們假設(shè)青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法 f(n)種跳法，那當(dāng) n = 0 時(shí)，f(0) = 0，沒(méi)有臺(tái)階當(dāng)然沒(méi)有跳法。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 開(kāi)始，是因?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)階有的跳法，然后從索引三開(kā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ī)劃的題目我們需要怎么做，我們一開(kāi)始定義了 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è)步驟，分別是
- 定義變量：把已知的和需要求解的，定義出變量，如上面的 n 和 f(n);
- 尋找表達(dá)式：找到 f(n) 和 f(n - 1) 以及 f(n - 2)，等情況的表達(dá)式，如上面的 f(n) = f(n - 1) + f(n - 2)，這一步往往是最難的;
- 尋找初始值：確保找到所有的臨界條件，如上面的 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)題，所以我們
- 定義 d[m][n] 表示在 m x n 網(wǎng)格上移到右下角需要的總步數(shù);
- 因?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];
- 定義初始值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 開(kāi)始
- return d[m - 1][n - 1];
- }
通過(guò)上面的三個(gè)步驟，我們可以完美的解決問(wèn)題，動(dòng)態(tài)規(guī)劃的問(wèn)題難點(diǎn)就在于找尋規(guī)律和初始值，有點(diǎn)時(shí)候如果我們找不到規(guī)律就沒(méi)辦法了，而且如果初始值找的不完全也會(huì)有問(wèn)題，這個(gè)只能多多練習(xí)了。
總結(jié)
動(dòng)規(guī)劃的題目在 LeetCode 上面有很多，大家可以根據(jù)上面提供的思路去多刷幾道題，慢慢就會(huì)有感覺(jué)了，刷完動(dòng)態(tài)規(guī)劃的題目，相信對(duì)大家工作或者找工作肯定有很大的幫助。
網(wǎng)站標(biāo)題：什么是動(dòng)態(tài)規(guī)劃——從青蛙跳臺(tái)階開(kāi)始了解
文章位置：http://www.5511xx.com/article/ccsdieo.html
