[[396723]]

本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者鴨血粉絲。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。

Hello 大家好，我是阿粉，動態(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. 定義變量：把已知的和需要求解的，定義出變量，如上面的 n 和 f(n);
2. 尋找表達(dá)式：找到 f(n) 和 f(n - 1) 以及 f(n - 2)，等情況的表達(dá)式，如上面的 f(n) = f(n - 1) + f(n - 2)，這一步往往是最難的;
3. 尋找初始值：確保找到所有的臨界條件，如上面的 f(0) = 0, f(1) = 1, f(2) = 2;

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

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

案例 2

問：一個機器人位于一個 m x n 網(wǎng)格的左上角 (起始點在下圖中標(biāo)記為“Start” )。機器人每次只能向下或者向右移動一步。機器人試圖達(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. 因為機器人只能向右和向下移動，所以到達(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ī)劃的題目，相信對大家工作或者找工作肯定有很大的幫助。