大家好我是蘇麟 , 今天聊聊動(dòng)態(tài)規(guī)劃 .

動(dòng)態(tài)規(guī)劃是最熱門(mén)、最重要的算法思想之一，在面試中大量出現(xiàn)，而且題目整體都偏難一些對(duì)于大部人來(lái)說(shuō)，最大的問(wèn)題是不知道動(dòng)態(tài)規(guī)劃到底是怎么回事。很多人看教程等，都被里面的狀態(tài)子問(wèn)題、狀態(tài)轉(zhuǎn)移方程等等勸退了。
其實(shí)，所謂的狀態(tài)就是一個(gè)數(shù)組，動(dòng)態(tài)規(guī)劃里的狀態(tài)轉(zhuǎn)移方程就是更新這個(gè)數(shù)組的方法。這一關(guān)，我們先理解動(dòng)態(tài)規(guī)劃到底怎么回事。

熱身 : 斐波那契數(shù)列

首先來(lái)感受一下什么是重復(fù)計(jì)算和記憶化搜索。

public class FibonacciTest {
    public static int count = 0;

    public static void main(String[] args) {
        fibonacci(20);
        System.out.println("count:" + count);
    }

    public static int fibonacci(int n) {
        System.out.println("斐波那契數(shù)列");
        count++;
        if (n == 0) {
            return 1;
        }
        if (n == 1 || n == 2)
            return n;
        else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

這個(gè)就是斐波那契數(shù)列，當(dāng)n為20時(shí)，count是21891次。而當(dāng)n=30 的時(shí)候結(jié)果是2692537，也就是接270萬(wàn)。如果純粹只是算斐波那契數(shù)列，我們可以直接循環(huán):

    public static int count_2 = 0;

    public int fibonacci(int n) {
        if (n <= 2) {
            count_2++;
            return n;
        }
        int f1 = 1;
        int f2 = 2;
        int sum = 0;
        for (int i = 3; i <= n; i++) {
            count_2++;
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }

n為30時(shí)也不過(guò)計(jì)算二十幾個(gè)數(shù)的累加，但是為什么采用遞歸竟然高達(dá)270萬(wàn)呢?
因?yàn)槔锩娲嬖诖罅康闹貜?fù)計(jì)算，數(shù)越大，重復(fù)越多。例如當(dāng)n=10的時(shí)候，我們看下面的結(jié)構(gòu)圖就已經(jīng)有很多重復(fù)計(jì)算了:

上面我們?cè)谟?jì)算f(10)時(shí)，可以看到f(9)、f(8)等等都需要計(jì)算，這就是重疊子問(wèn)題。怎么對(duì)其優(yōu)化一下呢?
可以看到這里主要的問(wèn)題是很多數(shù)據(jù)都會(huì)頻繁計(jì)算，如果將計(jì)算的結(jié)果保存到一個(gè)一維數(shù)組里。把 n 作為我們的數(shù)組下標(biāo)，f(n)作為值，也就是 arr[n] = f(n)。執(zhí)行的時(shí)候如果某人位置已經(jīng)被計(jì)算出來(lái)了就更新對(duì)應(yīng)位置的數(shù)組值，例如 f(4)算完了，就將其保存到arr[4]中，當(dāng)后面再次要計(jì)算 f(4) 的時(shí)候，我們判斷f(4)已經(jīng)計(jì)算過(guò)，因此直接讀取 f(4) 的值，不再遞歸計(jì)算。代碼如下:

        public static int[] arr = new int[50];
        public static int count_3 = 0;
        Arrays.fill(arr, -1);
        arr[0] = 1;
        int fibonacci ( int n){
            if (n == 2 || n == 1) {
                count_3++;
                arr[n] = n;
                return n;
            }
            if (arr[n] != -1) {
                count_3++;
                return arr[n];
            } else {
                count_3++;
                arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
                return arr[n];
            }
        }

在上面代碼里，在執(zhí)行遞歸之前先查數(shù)組看是否被計(jì)算過(guò)，如果重復(fù)計(jì)算了，就直接讀取，這就叫”記憶化搜索“，就這么簡(jiǎn)單。

路徑連環(huán)問(wèn)題

基本問(wèn)題 : 統(tǒng)計(jì)路徑總數(shù)

描述 :

一個(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)總共有多少條不同的路徑？

題目 :

LeetCode 62. 不同路徑 :

不同路徑

分析 :

我們先從一個(gè)3x2的情況來(lái)分析:

我們的目標(biāo)是從起點(diǎn)到終點(diǎn)，因?yàn)橹荒芟蛴一蛘呦蛳?，從圖中可以可以看到:

1.如果向右走，也就是圖1的情況，后面是一個(gè)3x1的矩陣，此時(shí)起點(diǎn)下面的兩個(gè)灰色位置就不會(huì)再訪問(wèn)了，只能從綠色位置一直向下走，只有一種路徑。

2.如果是向下走，我們可以看到原始起點(diǎn)右側(cè)的就不能再訪問(wèn)了，而剩下的又是一個(gè)2X2的矩陣，也就是從圖中綠色位置到紅色位置，此時(shí)仍然可以選擇向右或者向下，一共有兩種路徑。

所以上面的情況加起來(lái)就是一共有3種。

我們?cè)倏匆幌?X3的 :

可以看到，一個(gè)3X3的矩陣下一步就變成了一個(gè)3X2或者2X3的矩陣，而總路徑數(shù)，也是是兩者各自的路徑之和。
因此，對(duì)于一個(gè)mxn的矩陣，求路徑的方法search(m,n)就是:search(m-1,n)+search(m,n-1);
遞歸的含義就是處理方法不變，但是問(wèn)題的規(guī)模減少了

解析 :

注意 :遞歸的方式會(huì)超出時(shí)間限制

class Solution {
    public int uniquePaths(int m, int n) {
        return dp(m,n);
    }
    public int dp(int m,int n){
        if(n == 1 || m == 1){
            return 1;
        }
         return dp(m - 1,n) + dp(m,n - 1);
     }
} 

用二維數(shù)組優(yōu)化遞歸

我們來(lái)優(yōu)化遞歸的問(wèn)題，研究如何結(jié)合二維數(shù)組來(lái)實(shí)現(xiàn)記憶化搜索.

從上面這個(gè)樹(shù)也可以看到在遞歸的過(guò)程中存在重復(fù)計(jì)算的情況，例如1,1出現(xiàn)了兩次，如果是一個(gè)NXN的空間，那 1.0 和 0,1 的后續(xù)計(jì)算也是一樣的。從二維數(shù)組的角度，例如在位置(1,1)處，不管從(0,1)還是(1,0)到來(lái)，接下來(lái)都會(huì)產(chǎn)生2種走法，因此不必每次都重新遍歷才得到結(jié)果。

為此，我們可以采取一個(gè)二維數(shù)組來(lái)進(jìn)行記憶化搜索，算好的就記錄在數(shù)組中，也就是這樣子:

每個(gè)格子的數(shù)字表示從起點(diǎn)開(kāi)始到達(dá)當(dāng)前位置有幾種方式，這樣我們計(jì)算總路徑的時(shí)候可以先查一下二維數(shù)組有沒(méi)有記錄，如果有記錄就直接讀，沒(méi)有再計(jì)算，這樣就可以大量避免重復(fù)計(jì)算，這就是記憶化搜索

根據(jù)上面的分析，我們可以得到兩個(gè)規(guī)律:
1.第一行和第一列都是1。
2.其他格子的值是其左側(cè)和上方格子之和。對(duì)于其他m，n的格子，該結(jié)論一樣適用的，例如:

比如圖中的4，是有上面的1和左側(cè)的3計(jì)算而來(lái)，15是上側(cè)的5和左側(cè)的10計(jì)算而來(lái)。如果用公式表示就是:

解析 :

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] arr = new int[m][n];
        arr[0][0] = 1;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i > 0 && j > 0){
                    arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
                }else if(i > 0){
                    arr[i][j] = arr[i - 1][j];
                }else if(j > 0){
                    arr[i][j] = arr[i][j - 1];
                }
            }
        }
        return arr[m - 1][n - 1];
    }
} 

滾動(dòng)數(shù)組 : 用一維數(shù)組代替二維數(shù)組

我們通過(guò)滾動(dòng)數(shù)組來(lái)優(yōu)化此問(wèn)題。上面的緩存空間使用的是二維數(shù)組，這個(gè)占空間太大了，能否
進(jìn)一步優(yōu)化呢?
我們?cè)倏匆幌律厦娴挠?jì)算過(guò)程:

在上圖中除了第一行和第一列都是1外，每個(gè)位置都是其左側(cè)和上訪的格子之和，那我可以用一個(gè)大小為n的一維數(shù)組解決來(lái):

第一步，遍歷數(shù)組，將一維數(shù)組所有元素賦值為1

第二步，再次從頭遍歷數(shù)組，除了第一個(gè)，后面每個(gè)位置是其原始值和前一個(gè)位置之和，也就是這樣:

第三步:重復(fù)第二步:除了第一個(gè)，后面每個(gè)位置仍然是其原始值和前一個(gè)位置之和，也就是這樣:

• 繼續(xù)循環(huán)，題目給的m是幾就循環(huán)幾次，要得到結(jié)果，輸出最后一個(gè)位置的15就可以了.

上面這幾個(gè)一維數(shù)組拼接起來(lái)，是不是發(fā)現(xiàn)和上面的二維數(shù)組完全一樣的? 而這里我們使用了一個(gè)一維數(shù)組就解決了，這種反復(fù)更新數(shù)組的策略就是滾動(dòng)數(shù)組.計(jì)算公式是:

解析 :

class Solution {
    public int uniquePaths(int m, int n) {
        int[] arr = new int[n];
        Arrays.fill(arr,1);
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                arr[j] = arr[j - 1] + arr[j];
            }
        }
        return arr[n - 1];
    }
} 

拓展問(wèn)題 : 最小路徑和

描述 :

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

題目 :

LeetCode 64. 最小路徑和 :

最小路徑和 :

分析 :

這道題是在上面題目的基礎(chǔ)上，增加了路徑成本概念。由于題目限定了我們只能[往下]或者[往右]移動(dòng)，因此我們按照當(dāng)前位置可由哪些位置轉(zhuǎn)移過(guò)來(lái) 進(jìn)行分析:

• 當(dāng)前位置只能通過(guò)[往下] 移動(dòng)而來(lái)，即有f[i][j] = f[i-1][j] + grid[i][j]
• 當(dāng)前位置只能通過(guò)[往右]移動(dòng)而來(lái)，即有 f[i][j] = f[i][j-1] + grid[i][j]
• 當(dāng)前位置既能通過(guò)[往下]也能[往右] 移動(dòng)，即有f[i][j] = min(f[i][j - 1],f[i - 1][j]) + grid[i][j]

二維數(shù)組的更新過(guò)程，我們可以圖示一下:

我們現(xiàn)在可以引入另外一個(gè)概念狀態(tài): 所謂狀態(tài)就是下面表格更新到最后的二維數(shù)組,而通過(guò)前面格子計(jì)算后面格子的公式就叫狀態(tài)轉(zhuǎn)移方程。如果用數(shù)學(xué)表達(dá)就是:

所謂的確定狀態(tài)轉(zhuǎn)移方程就是要找遞推關(guān)系，通常我們會(huì)從分析首尾兩端的變化規(guī)律來(lái)入手。

解析 :

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] arr = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i == 0 && j == 0){
                    arr[i][j] = grid[i];
                }else{
                    int top = i - 1 >= 0 ? arr[i - 1][j] + grid[i][j] : Integer.MAX_VALUE; 
                    int left = j - 1 >= 0 ? arr[i][j - 1] + grid[i][j] :
Integer.MAX_VALUE;
                    arr[i][j] = Math.min(top,left);
                }
            }
        }

        return arr[m - 1][n - 1];
    }
}

理解動(dòng)態(tài)規(guī)劃

DP能解決哪類(lèi)問(wèn)題? 直觀上，DP一般是讓找最值的，例如最長(zhǎng)公共子序列等等，但是最關(guān)鍵的是DP問(wèn)題的子問(wèn)題不是相互獨(dú)立的，如果遞歸分解直接分解會(huì)導(dǎo)致重復(fù)計(jì)算指數(shù)級(jí)增長(zhǎng)。而DP最大的價(jià)值是為了消除冗余，加速計(jì)算 .

這期就到這里下期見(jiàn) !文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-774828.html

到了這里，關(guān)于算法通關(guān)第十九關(guān)-青銅挑戰(zhàn)理解動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！