每一種算法都最好看完第一篇再去找要看的博客，因?yàn)檫@樣會(huì)幫你梳理好思路，看接下來的博客也就更輕松了。當(dāng)然，我也會(huì)盡量在寫每一篇時(shí)都可以讓不懂這個(gè)算法的人也能邊看邊理解。

1、動(dòng)規(guī)思路簡(jiǎn)介

動(dòng)規(guī)的思路有五個(gè)步驟，且最好畫圖來理解細(xì)節(jié)，不要怕麻煩。當(dāng)你開始畫圖，仔細(xì)閱讀題時(shí)，學(xué)習(xí)中的沉浸感就體驗(yàn)到了。

狀態(tài)表示
狀態(tài)轉(zhuǎn)移方程
初始化
填表順序
返回值

動(dòng)規(guī)一般會(huì)先創(chuàng)建一個(gè)數(shù)組，名字為dp，這個(gè)數(shù)組也叫dp表。通過一些操作，把dp表填滿，其中一個(gè)值就是答案。dp數(shù)組的每一個(gè)元素都表明一種狀態(tài)，我們的第一步就是先確定狀態(tài)。

狀態(tài)的確定可能通過題目要求來得知，可能通過經(jīng)驗(yàn) + 題目要求來得知，可能在分析過程中，發(fā)現(xiàn)的重復(fù)子問題來確定狀態(tài)。還有別的方法來確定狀態(tài)，但都大同小異，明白了動(dòng)規(guī)，這些思路也會(huì)隨之產(chǎn)生。狀態(tài)的確定就是打算讓dp[i]表示什么，這是最重要的一步。狀態(tài)表示通常用某個(gè)位置為結(jié)尾或者起點(diǎn)來確定，這點(diǎn)在下面的題解中慢慢領(lǐng)會(huì)。

狀態(tài)轉(zhuǎn)移方程，就是dp[i]等于什么，狀態(tài)轉(zhuǎn)移方程就是什么。像斐波那契數(shù)列，dp[i] = dp[i - 1] + dp[i - 2]。這是最難的一步。一開始，可能狀態(tài)表示不正確，但不要緊，大膽制定狀態(tài)，如果沒法推出轉(zhuǎn)移方程，沒法得到結(jié)果，那這個(gè)狀態(tài)表示就是錯(cuò)誤的。所以狀態(tài)表示和狀態(tài)轉(zhuǎn)移方程是相輔相成的，可以幫你檢查自己的思路。

要確定方程，就從最近的一步來劃分問題。

初始化，就是要填表，保證其不越界。像第一段所說，動(dòng)規(guī)就是要填表。比如斐波那契數(shù)列，如果要填dp[1]，那么我們可能需要dp[0]和dp[-1]，這就出現(xiàn)越界了，所以為了防止越界，一開始就固定好前兩個(gè)值，那么第三個(gè)值就是前兩個(gè)值之和，也不會(huì)出現(xiàn)越界。初始化的方式不止這一點(diǎn)，有些問題，假使一個(gè)位置是由前面2個(gè)位置得到的，我們初始化最一開始兩個(gè)位置，然后寫代碼，會(huì)發(fā)現(xiàn)不夠高效，這時(shí)候就需要設(shè)置一個(gè)虛擬節(jié)點(diǎn)，一維數(shù)組的話就是在數(shù)組0位置處左邊再填一個(gè)位置，整個(gè)dp數(shù)組的元素個(gè)數(shù)也+1，讓原先的dp[0]變?yōu)楝F(xiàn)在的dp[1]，二維數(shù)組則是要填一列和一行，設(shè)置好這一行一列的所有值，原先數(shù)組的第一列第一行就可以通過新填的來初始化，這個(gè)初始化方法在下面的題解中慢慢領(lǐng)會(huì)。

第二種初始化方法的注意事項(xiàng)就是如何初始化虛擬節(jié)點(diǎn)的數(shù)值來保證填表的結(jié)果是正確的，以及新表和舊表的映射關(guān)系的維護(hù)，也就是下標(biāo)的變化。

填表順序。填當(dāng)前狀態(tài)的時(shí)候，所需要的狀態(tài)應(yīng)當(dāng)已經(jīng)計(jì)算過了。還是斐波那契數(shù)列，填dp[4]的時(shí)候，dp[3]和dp[2]應(yīng)當(dāng)都已經(jīng)計(jì)算好了，那么dp[4]也就出來了，此時(shí)的順序就是從左到右。還有別的順序，要依據(jù)前面的分析來決定。

返回值，要看題目要求。

2、不同路徑

62. 不同路徑

這是一個(gè)很經(jīng)典的題目了，還有類似的題目是走迷宮，可走的路徑上都是0，代表墻的就是1。

每一步都可以是向右或者向下。動(dòng)規(guī)（1）中狀態(tài)的表示我們分為以i位置為結(jié)尾或者起點(diǎn)，但這里是一個(gè)二維的空間，所以就變成以[i, j]為結(jié)尾或起點(diǎn)，這道題我們把[i, j]當(dāng)作結(jié)尾。

題目中需要求到達(dá)右下角時(shí)有多少條路徑。在分析狀態(tài)轉(zhuǎn)移方程時(shí)，我們采用最近的一步來分析問題。到達(dá)一個(gè)點(diǎn)只能是左邊的節(jié)點(diǎn)向右走，或者上面的節(jié)點(diǎn)向下走，才能走到這個(gè)節(jié)點(diǎn)，而左邊或者上面的節(jié)點(diǎn)也同樣是這兩種情況走過來的，所以對(duì)于這個(gè)題，狀態(tài)的表示就可以理解成dp[i, j]等于到達(dá)這個(gè)位置的路徑數(shù)，而狀態(tài)轉(zhuǎn)移方程要如何確定？如果是從左邊節(jié)點(diǎn)向右移動(dòng)過來的，那么這個(gè)節(jié)點(diǎn)的路徑數(shù)應(yīng)當(dāng)是左邊這個(gè)節(jié)點(diǎn)的路徑數(shù)，為什么不加1？要注意，走一步和路徑是兩個(gè)概念，左邊節(jié)點(diǎn)代表著來到這個(gè)節(jié)點(diǎn)的路徑數(shù)，這些路徑都只需要再往右走一步即可，不需要再新增一個(gè)路徑，所以只是路徑改變了，但是數(shù)量不變，所以dp[i][j] = dp[i][j - 1]。上面的節(jié)點(diǎn)向下走一步也同理，dp[i][j] = dp[i - 1][j]。所以狀態(tài)轉(zhuǎn)移方程就是dp[i][j - 1] + dp[i - 1][j] = dp[i][j]。

第一行和第一列的節(jié)點(diǎn)可不全是由這兩種情況演變過來的，第一列的節(jié)點(diǎn)的左邊就越界了，所以我們可以先把第一行第一列的所有位置給初始化固定的數(shù)值，然后再一步步向右下角計(jì)算。另一種方法就是設(shè)立虛擬節(jié)點(diǎn)，創(chuàng)建數(shù)組時(shí)多創(chuàng)建一行一列，初始化新表的第一行第一列，那么舊表的第一行第一列就可以通過新表的第一行第一列來計(jì)算得到，計(jì)算公式就是dp[i][j - 1] + dp[i - 1][j] = dp[i][j]。，然后向右下角逐漸計(jì)算。

現(xiàn)在看貌似第二種方法也不是很高效，這只是因?yàn)楝F(xiàn)在這樣的題沒法看出來，有些題目用第二種方式代碼會(huì)更簡(jiǎn)潔。

這道題我們就用第二種方式來寫。根據(jù)上面的分析，狀態(tài)表示就是dp[i, j]代表到達(dá)這個(gè)位置的路徑數(shù)，狀態(tài)轉(zhuǎn)移方程是dp[i][j - 1] + dp[i - 1][j] = dp[i][j]。，初始化時(shí)多創(chuàng)建一行一列，填表順序是從上往下填寫每一行，每一行從左到右填寫，返回值就是右下角那個(gè)位置的值。

這里面還剩初始化的問題沒有解決，原數(shù)組中第一行第一列，它們的每個(gè)位置應(yīng)當(dāng)都是1，它們只可能是從左邊或者從上面沒移動(dòng)過來的，所以只能是1，而新增的第一行第一列要如何設(shè)置數(shù)值來讓它們都是1？其實(shí)我們只需要確定新表中第二行第二列的那個(gè)數(shù)就行，因?yàn)槌サ谝恍械谝涣校渌鼣?shù)字都可以通過它來得到，所以可以這樣設(shè)置

分析完成，寫代碼

    int uniquePaths(int m, int n){
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1;j <= n; j++)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }

3、不同路徑Ⅱ

63. 不同路徑 II

狀態(tài)表示是到達(dá)[i, j]時(shí)一共有多少種方法。狀態(tài)轉(zhuǎn)移方程有所改變。如果[i, j]是障礙物，那么就沒法到這個(gè)位置，也就是0；如果不是障礙物，那就和上一個(gè)題一樣，dp[i][j - 1] + dp[i - 1][j] = dp[i][j]，但如果上面或者左邊是障礙物怎么辦？其實(shí)沒影響，因?yàn)槿绻钦系K物，那個(gè)位置就是0，加上0不影響最終結(jié)果。其實(shí)和上一個(gè)題比較，唯一的不同就是某個(gè)位置為障礙物就為0。

初始化時(shí)設(shè)立虛擬節(jié)點(diǎn)，增加一行一列，和上一道題一樣，保證第二行第二列那個(gè)值正確就行。所以和上面的代碼一樣，dp[0][1] = 1或者dp[1][0] = 1就行。

填表順序和上面一樣，映射關(guān)系要處理好，返回值就是右下角那個(gè)值。

    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        int m = ob.size(), n = ob[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[1][0] = 1;
        for(int i = 1; i <= m ; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(ob[i - 1][j - 1] == 0)//體現(xiàn)了映射關(guān)系，我們需要都減去1才能找到原表的元素
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else dp[i][j] = 0;
            }
        }
        return dp[m][n];
    }

4、禮物的最大價(jià)值

劍指 Offer 47. 禮物的最大價(jià)值

這個(gè)題和不同路徑那個(gè)題相似。題目要求計(jì)算走到右下角最多能拿到多少，只能走右邊或者下邊。對(duì)于右下角那個(gè)位置的數(shù)值，它能拿到的最大價(jià)值要從上面節(jié)點(diǎn)和左面節(jié)點(diǎn)中選擇，也就是這兩個(gè)中的較大值，再加上右下角位置的本身數(shù)值，就是最大的價(jià)值。既然是這樣的思路，那么上面和左面的節(jié)點(diǎn)就得是到這個(gè)節(jié)點(diǎn)時(shí)最大的價(jià)值，所有狀態(tài)表示就是dp[i][j]是到達(dá)這個(gè)位置時(shí)的最大價(jià)值。

根據(jù)上面的分析，當(dāng)前位置的最大價(jià)值是上面和左面節(jié)點(diǎn)的較大值，再加上當(dāng)前位置的價(jià)值，所以狀態(tài)轉(zhuǎn)移方程就是dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + 當(dāng)前位置的價(jià)值。

初始化時(shí)，我們還是采用多加一行多加一列的方式，這個(gè)方法的注意事項(xiàng)就是新增行列的值要保證后面位置的值要正確，以及新表和舊表的映射關(guān)系。原表已經(jīng)在每個(gè)位置都放上了對(duì)應(yīng)的數(shù)值，如果新增行列的話，應(yīng)當(dāng)不影響原先的數(shù)值，所以都設(shè)置為0，而vector默認(rèn)初始化為0。

填表順序就是每一列從上到下，每一行從左到右，返回值則是右下角那個(gè)值。

    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

5、下降路徑最小和

931. 下降路徑最小和

看題目可能比較懵，但好在題目最后給了公式。從公式中看出來，一個(gè)值和要比較的三個(gè)值之間呈現(xiàn)一個(gè)三角形，一個(gè)位置可能由上面3個(gè)位置而來，雖然題目中給的是一個(gè)值和下面三個(gè)值的關(guān)系，但我們把它反過來也一樣，就變成了一個(gè)值和上面3個(gè)值。

狀態(tài)表示還是到達(dá)[i, j]位置時(shí)最小的下降路徑。狀態(tài)轉(zhuǎn)移方程題目已經(jīng)給了，dp[i][j] = 上面三個(gè)位置的最小值再加上當(dāng)前位置的數(shù)值，這三個(gè)位置分別是dp[i - 1][j - 1]，dp[i - 1][j]，dp[i - 1][j + 1]，找出這個(gè)三個(gè)的最小值就行。

初始化是為了防止越界問題，這次的初始化有所不同，不能直接一行，一列，而是要讓新加的行列把整個(gè)表包圍起來，左右邊各新增一列，上面新增一行。如何初始化新增的行列？對(duì)于最上面一行來說，也就是新增的行，它不能影響原表第一行的元素，所以都為0；而對(duì)于新增的列來說，不能為0，因?yàn)槲覀円氖亲钚≈?，新增的列的?shù)值不應(yīng)當(dāng)影響比較，所以我們把它初始化為正無(wú)窮大。初始化時(shí)先都設(shè)為正無(wú)窮，然后再把第一行全設(shè)為0就行。新增行列后，原表中的[0, 0]變?yōu)樾卤淼腫1, 1]，所以新表的[i, j]對(duì)應(yīng)原表的[i - 1][j - 1]。

填表順序是從上到下。返回值不是右下角的值，因?yàn)檫@個(gè)題要求到達(dá)最后一行，所以要取最后一行的最小值就行。

    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        for(int j = 0; j < n + 2; j++)
        {
            dp[0][j] = 0;
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(min(dp[i - 1][j], dp[i - 1][j + 1]), dp[i - 1][j - 1]) + matrix[i - 1][j - 1];
            }
        }
        int ret = INT_MAX;
        for(int j = 1; j <= n; j++)
        {
            ret = min(ret, dp[n][j]);
        }
        return ret;
    }

6、最小路徑和

64. 最小路徑和

這道題和禮物的最大價(jià)值是一個(gè)題，只不過一個(gè)求最大，一個(gè)求最小。不過需要注意的是，如果是求最大，我們把新增行列初始化為0，然后找特殊位置；而求最小，則是初始化為正無(wú)窮，然后找特殊位置。這個(gè)題的特殊位置就是像上圖中的左上角位置，它的數(shù)值是1，即使加上新增行列中的對(duì)應(yīng)的兩個(gè)位置的較小值也不能被改變數(shù)值，所以新表dp[0][1] = dp[1][0] = 1。其余新增位置設(shè)為正無(wú)窮即可。

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

7、地下城游戲

174. 地下城游戲

這個(gè)題看起來稍有點(diǎn)不一樣。狀態(tài)表示應(yīng)該是什么？還是以某個(gè)位置為結(jié)尾或者為起點(diǎn)。如果是為結(jié)尾，意思是從起點(diǎn)出發(fā)，到[i, j]位置時(shí)，所需的最低初始健康點(diǎn)數(shù)是多少。我們需要用到上面和左面位置來更新當(dāng)前位置的值，但實(shí)際上卻不止這點(diǎn)，因?yàn)榧词刮覀兯愠鰜懋?dāng)前位置的值，我們還需要考慮右面或者下面節(jié)點(diǎn)的值，如果它們是個(gè)-100，那么很有可能直接死亡，那又得重新計(jì)算了，可以自己列舉幾個(gè)數(shù)字，按照一條路線試著走，會(huì)發(fā)現(xiàn)需要不斷再改變初始值，再走一遍。所以這個(gè)題適合以當(dāng)前節(jié)點(diǎn)為起點(diǎn)，從[i, j]位置出發(fā)，到達(dá)終點(diǎn)，所需的最低初始健康值，每一步都可能是往右或者往下，當(dāng)前位置的值要選擇右邊位置和下邊位置的較小值，并且還要考慮當(dāng)前位置的值，因?yàn)楫?dāng)前位置還沒過去，所以假設(shè)x是最低初始值，那么僅看一條路線，x + 原數(shù)組[i][j] >= dp[i][j + 1]，也就是x >= dp[i][j + 1] - 原數(shù)組[i][j]，那么往下走就是x >= dp[i + 1][j] - 原數(shù)組[i][j]，求右邊和下邊的較小值就可，但這里仍然有坑點(diǎn)，如果當(dāng)前位置的值是個(gè)負(fù)數(shù)呢？我們走到這里，可能直接死亡了，所以我們要更換一下dp[i][j]，讓它和1取較大值，把一個(gè)負(fù)數(shù)變成1，因?yàn)槲覀冞€要走下去，要至少有一點(diǎn)血量才行。如果走到當(dāng)前位置，dp[i][j]是正數(shù)，這沒問題，但如果是負(fù)數(shù)，說明掛了，我們就得改為1，這樣就能保證一路上掛不了，也能求出來最低初始值。

初始化時(shí)還是多加一列多加一行，但因?yàn)楸容^的值是右邊和下邊的，所以我們要在舊表的右邊和下邊添加一列一行，并且這時(shí)候就不用考慮映射關(guān)系了，因?yàn)榕f表的元素在新表的下標(biāo)還是一樣。特殊位置是在右下角那個(gè)值，走到右下角時(shí)，我們要保證血量還剩至少1，那么它的右邊和下邊就得是1，而其他位置，因?yàn)榍笞钚≈担詾榱瞬挥绊懹?jì)算，就初始化成正無(wú)窮。

填表順序和之前不一樣，應(yīng)當(dāng)是每列從下往上，每行從右往左填。返回值是左上角那個(gè)值。

    int calculateMinimumHP(vector<vector<int>>& dg) {
        int m = dg.size(), n = dg[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dg[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }

結(jié)束。文章來源地址http://www.zghlxwxcb.cn/news/detail-737627.html

到了這里，關(guān)于C++算法 —— 動(dòng)態(tài)規(guī)劃（2）路徑問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！