目錄

??今日良言：天會晴，心會暖

??一、什么是動態(tài)規(guī)劃

??二、如何使用動態(tài)規(guī)劃

??三、典型例題

??今日良言：天會晴，心會暖

??一、什么是動態(tài)規(guī)劃

動態(tài)規(guī)劃（Dynamic Programming，簡稱DP）是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)動態(tài)規(guī)劃（Dynamic Programming，簡稱DP）是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。它是一種利用重復(fù)子問題的性質(zhì)來求解復(fù)雜問題的算法思想。

上述只是對于動態(tài)規(guī)劃進(jìn)行一個官方解釋，接下來博主介紹一下動態(tài)規(guī)劃的基本思想：

將一個復(fù)雜的問題分解成一系列相互重疊的子問題，然后將子問題的解決方案組合起來，形成整個問題的解決方案。

??二、如何使用動態(tài)規(guī)劃

上述簡單的了解了動態(tài)規(guī)劃之后，是不是一頭霧水？不要著急，繼續(xù)往下看，待博主細(xì)細(xì)道來。

動態(tài)規(guī)劃通常用于優(yōu)化一下問題，比如：最短路徑、最長公共子序列、背包問題等。

使用動態(tài)規(guī)劃解決問題的步驟一般都是固定的，一般是如下五個解決步驟：

1.狀態(tài)表示

2.狀態(tài)轉(zhuǎn)移方程

3.初始化

4.填表順序

5.返回值

接下來，我將依次介紹這五個步驟的內(nèi)容。

?1.狀態(tài)表示

在解決動態(tài)規(guī)劃問題的時候，一般會創(chuàng)建一個dp表（一維數(shù)組或者二維數(shù)組），這里先用簡單的一維數(shù)組。

解決動態(tài)規(guī)劃就是將這個dp表中的數(shù)據(jù)填滿，其中，狀態(tài)表示就是dp表中每個位置的值代表的含義。

大多數(shù)對于狀態(tài)表示的解釋都比較晦澀難懂，這里感性的理解成博主上述表達(dá)的意思，通過大量做題來深刻理解狀態(tài)表示。

知道了狀態(tài)表示是什么，就需要考慮狀態(tài)表示如何得到？

主要有以下三個方向：

1）題目要求

? ? ?一般題目有些題目會給出狀態(tài)表示

2）經(jīng)驗(yàn) + 題目要求

? ? ?通過大量的做題積累經(jīng)驗(yàn)，水到而渠成。

3）分析子問題的過程中，發(fā)現(xiàn)重復(fù)的子問題。

? ? ? 將這個重復(fù)的子問題抽象成狀態(tài)表示。

通過一道最簡單的動態(tài)規(guī)劃入門例題來解釋上述比較抽象的概念：

在這道題中，可以直接根據(jù)題目要求（返回第n個泰波那契數(shù)）來得到狀態(tài)表示。在dp表中，dp[0] 表示第一個泰波那契數(shù)，dp[1]表示第二個泰波那契數(shù)......dp[i]表示第i個泰波那契數(shù)。由此，就可以得到狀態(tài)表示：

dp[i]表示：第 i?個泰波那契數(shù)的值。

狀態(tài)表示是解決動態(tài)規(guī)劃問題的第一步，至關(guān)重要，與狀態(tài)轉(zhuǎn)移方程相比的重要程度不遑多讓，如果連狀態(tài)表示都找不出，整個狀態(tài)轉(zhuǎn)移方程就無法解決了。

2.狀態(tài)轉(zhuǎn)移方程

?之前接觸過動態(tài)規(guī)劃問題或者做過相關(guān)例題的老鐵應(yīng)該知道狀態(tài)轉(zhuǎn)移方程的重要性，狀態(tài)轉(zhuǎn)移方程決定了如何解決動態(tài)規(guī)劃問題，對于狀態(tài)轉(zhuǎn)移方程的尋找可謂是至關(guān)重要。

對于狀態(tài)轉(zhuǎn)移方程的解釋可以簡單理解一下：

狀態(tài)轉(zhuǎn)移方程就是 dp[i] 等于什么

以上述例題為例，這里已經(jīng)告訴了dp[i] 等于什么：

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

上述這個公式就是狀態(tài)轉(zhuǎn)移方程

上述是解決動態(tài)規(guī)劃問題的兩個核心步驟，接下來介紹剩余的三個細(xì)節(jié)步驟。?

?3.初始化

“保證填dp表的時候不越界”

根據(jù)狀態(tài)轉(zhuǎn)移方程來進(jìn)行dp表中的一些位置的初始化，避免發(fā)生越界錯誤。這個小步驟需要和狀態(tài)轉(zhuǎn)移方程結(jié)合來進(jìn)行。

對于上述狀態(tài)轉(zhuǎn)移方程：?dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

如果通過這個狀態(tài)轉(zhuǎn)移方程填dp[0] 位置，就會出現(xiàn) dp[0] = dp[-3] + dp[-2] + dp[-1]?，顯然發(fā)生了越界錯誤，因此，在填dp表的時候需要先對表中的一些位置進(jìn)行初始化。??

對于這道例題來說，需要初始化的位置有前三個（dp[0] dp[1] dp[2]），并且具體初始化的值在題目中已經(jīng)給出，直接初始化dp[0] = 0，dp[1] = dp[2] = 1

4.填表順序

?“為了填寫當(dāng)前狀態(tài)的時候，所需要的狀態(tài)已經(jīng)計(jì)算過了”

以上面的例題為例，在dp表中，前三個位置已經(jīng)初始化了，此時，如果博主想要填dp[4]這個位置，需要依賴前三個位置:dp[1] dp[2]? dp[3]

?但是dp[3] 還沒有進(jìn)行填表，因此需要先填dp[3] 然后再填dp[4],由此可以得到填這個dp表的順序是：從左到右。并且開始填表的位置是dp[3].

5.返回值

? “題目要求 + 狀態(tài)表示”

以上面的例題來看，題目要求：返回第n個泰波那契數(shù)的值。狀態(tài)表示dp[i]：第i個泰波那契數(shù)的值。 因此，這道題目就返回dp[n] 的值即可。

?上述五個步驟就是使用動態(tài)規(guī)劃解決問題的步驟，這五個步驟需要頻繁且大量的練習(xí)動態(tài)規(guī)劃題目，通過大量的經(jīng)驗(yàn)來加深理解。

對于動態(tài)規(guī)劃問題編寫代碼的順序一般也可以分五個步驟：

1.避免越界

2.創(chuàng)建dp表

3.初始化

4.填表

5.返回值

通過解決上述例題的代碼來加深理解

class Solution {
    public int tribonacci(int n) {
        // 1.避免越界
        if (n == 0 || n == 1) {
            return n;
        }
        // 2.創(chuàng)建dp表
        // 由于要求第n個位置，因此創(chuàng)建n+1大小的數(shù)組
        int[] dp = new int[n+1];
        // 3.初始化
        // 初始化前三個位置
        dp[0] = 0;dp[1] = dp[2] = 1;
        // 4.填表
        // 從dp[3] 位置開始填表
        for (int i = 3; i <= n;i++) {
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }
        // 5.返回值
        // 返回dp[n]
        return dp[n];
    }
}

以上解釋解決一道動態(tài)規(guī)劃問題的基本流程，剛接觸動態(tài)規(guī)劃問題的老鐵如果不知道如何下手，可以先按照上述流程寫一個模版來嘗試解決問題。?

接下來，博主將選擇幾道比較經(jīng)典的動態(tài)規(guī)劃問題來熟悉上述流程。

??三、典型例題

1.路徑問題

路徑問題是動態(tài)規(guī)劃比較經(jīng)典的例題，如下鏈接：

LCR 098. 不同路徑 - 力扣（LeetCode）

這里雖然是二維數(shù)組問題，但是上述解決動態(tài)規(guī)劃問題的步驟依舊適用。

1.狀態(tài)表示

狀態(tài)表示是找dp表中每個位置的值代表的含義，根據(jù)題目要求可知：dp表中存的是到達(dá)某個位置的不同路徑數(shù)目，由于是二維數(shù)組，每個位置需要通過橫縱坐標(biāo)組合表示，因此，可以得到：dp[i][j] 表示： 到達(dá)i j 位置的不同路徑的數(shù)目。

上述就是狀態(tài)表示。

2.狀態(tài)轉(zhuǎn)移方程

找狀態(tài)轉(zhuǎn)移方程就是找dp[i][j] 等于什么，分析題目，對于每一個位置來說：可以通過機(jī)器人所處的上一個位置往下一步，或者左邊一個位置往右一步可以得到。

也就是說: dp[i][j] 這個位置可以從dp[i-1][j] 往下一步? 或者 dp[i][j-1] 這個位置往右一步。

題目要求總共的路徑條數(shù)，因此，狀態(tài)轉(zhuǎn)移方程就是：dp[i][j] = dp[i-1][j] + dp[i][j-1]

3.初始化

初始化是為了避免越界，在初始化時，可以根據(jù)狀態(tài)轉(zhuǎn)移方程來進(jìn)行初始化，在狀態(tài)轉(zhuǎn)移方程中，假設(shè)要求dp[0][0]，根據(jù)狀態(tài)轉(zhuǎn)移方程: dp[0][0] = dp[-1][0] + dp[0][-1]? 會發(fā)現(xiàn)越界問題，為了避免越界問題，在填二維dp表的時候，可以采取的策略是多開一行和一列。

假設(shè)題目給的是一個 5?X 4 的網(wǎng)格，需要創(chuàng)建出一個 5X 4的如下dp表：

但是 5?X 4 的dp表在初始化的時候會發(fā)生越界訪問，因此采取多開一行和一列的策略：創(chuàng)建一個 6?X 5 的dp表：

對于這個dp表來說，需要填的部分是圖中黑色網(wǎng)格，紅色的不用填，也就是實(shí)際開始填的位置是dp[1][1]，但是dp[1][1] 依賴dp[1][0] 和 dp[0][1] 這兩個位置，由于機(jī)器人到達(dá)第一個位置，它的路徑只有一條，因此，將dp[1][0] 和 dp[0][1] 其中的一個值初始化為1，來進(jìn)行填表。假設(shè)dp[0][1] = 1:

上述就是初始化操作。

4.填表順序

假設(shè)現(xiàn)在要填 dp[3][4] 這個位置，根據(jù)狀態(tài)轉(zhuǎn)移方程來考慮，需要先填dp[2][4] 和dp[3][3] 位置，因此，可以得出填表順序是：從左到右并且從上往下。

5.返回值

根據(jù)題目要求，需要返回到達(dá)[m-1][n-1] 位置的不同路徑數(shù)目，結(jié)合狀態(tài)表示（dp[i][j]表示到達(dá)i j位置的不同路徑數(shù)目），應(yīng)該返回dp[m-1][n-1]。但是，由于dp表多開了一行和一列，最終返回的結(jié)果應(yīng)該是dp[m][n]。

上述就是整個解決此道動態(tài)規(guī)劃的分析流程，編寫代碼如下：

class Solution {
    public int uniquePaths(int m, int n) {
        // 1.創(chuàng)建dp表
        // 需要多開一行和一列
        int[][] dp = new int[m+1][n+1];
        // 2.初始化
        // 需要初始化dp[0][1] 或者 dp[1][0]
        dp[0][1] = 1;
        // 3.填表
        //   從 1 1 位置開始填
        for(int i = 1; i <= m;i++) {
            for (int j = 1; j <= n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        // 4.返回值
        return dp[m][n];
    }
}

以上就是路徑問題一道比較經(jīng)典的例題解法。

2.簡單多狀態(tài)問題

如下例題：

面試題 17.16. 按摩師 - 力扣（LeetCode）

接下來，使用五步法來解決這道例題：

1.狀態(tài)表示

分析題目要求：給定的數(shù)組表示預(yù)約時間，通過選擇這個數(shù)組中的一些元素來獲得最大的總時長。對于實(shí)例1（【1,2,3,4】）來說，可以先選擇第一個位置，然后第二個位置不能選，再選擇第三個位置，第四個位置不選，這樣最終得到的時長是最大的。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

上述是分析題目要求的，接下來找狀態(tài)表示：

根據(jù)經(jīng)驗(yàn)+題目要求，dp表中存的是選擇每個位置的最長預(yù)約時間，對于該題來說，狀態(tài)表示（dp[i]）是：選擇到 i 位置的時候，此時的最長預(yù)約時間。

狀態(tài)表示找到了，但是需要注意，在題目中有這樣一個要求：

對于每個位置來說，按摩師都有兩種選擇：接或者不接。因此可以劃分出兩個狀態(tài)，對于這種情況，我們常用的策略是：根據(jù)狀態(tài)的數(shù)量來創(chuàng)建dp表的數(shù)目。對于這道題來說，可以創(chuàng)建兩張dp表：

f[i] 表示：選擇到 i 位置的時候，選nums[i],此時的最長預(yù)約時間。

g[i]表示：選擇到 i 位置的時候，不選nums[i],此時的最長預(yù)約時間。

2.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程就是找dp[i]等于什么，套用到這道題，也就是找f[i] 和 g[i] 等于什么。

f[i] 表示的是到 i 位置時，選nums[i] 這個預(yù)約時間，此時的最長預(yù)約時間。那么i - 1 這個位置就不能選擇了，因此，f[i] = g[i-1] + nums[i]? (這里的意思是當(dāng)前f[i] 的值，就等于前面i-1位置不選擇的最長預(yù)約時間 + 當(dāng)前nums[i] )

g[i] 表示的是到i - 1 位置時，不選nums[i]這個預(yù)約時間，此時的最長預(yù)約時間，那么i - 1這個位置就有兩種選擇：選擇 i - 1 或者不選 i -1，因此，g[i] = f[i-1]??（不選i位置并且選擇i-1位置的最長預(yù)約時間）或者 g[i] = g[i-1] (不選i位置并且不選i-1位置的最長預(yù)約時間)

由于要求最長預(yù)約時間，也就是上述兩種情況的最大值，因此：

g[i] = Math.max(f[i-1],g[i-1])

3.初始化

根據(jù)狀態(tài)轉(zhuǎn)移方程來進(jìn)行初始化，在狀態(tài)轉(zhuǎn)移方程中，出現(xiàn)了 i - 1 就需要考慮是否越界，通常的做法是給數(shù)組多開一個位置，但是這道題由于初始化比較簡單，所以就不需要多開一個位置，直接根據(jù)狀態(tài)轉(zhuǎn)移方程初始化即可。

f[0] 表示的是選擇到0位置，選nums[0],此時的最長預(yù)約時間，則f[0] = nums[0]

g[0] 表示的是選擇到0為止，不選nums[0]，此時的最長預(yù)約時間,則g[0] = 0

后續(xù)填表的時候，從1下標(biāo)開始填即可。

4.填表順序

由于有兩張dp表，又因?yàn)檫@兩張dp表直接有依賴關(guān)系，因此需要兩張表一起填。

假設(shè)要填f[3] 和 g[3] 這兩個位置，那么g[2] 和 f[2] 這兩個位置需要先填，因此，填表順序就是：從左到右且兩表同時填。

5.返回值?

題目要求返回的是最長的預(yù)約時間，由于有兩張表，因此需要返回兩張表最后一個位置的較大值（最后一個位置選擇或者不選擇有兩種情況，需要求這兩種情況的最大值）。

上述就是整個解決此道動態(tài)規(guī)劃的分析流程，編寫代碼如下：

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0; 
        // 1.創(chuàng)建dp表
        // 兩張表
        int[] f = new int[n];
        int[] g = new int[n];
        // 2.初始化
        f[0] = nums[0];
        g[0] = 0;// 表中數(shù)據(jù)默認(rèn)就是0
        // 3.填表
        // 從1下標(biāo)開始填，同時填
        for (int i = 1; i < n;i++) {
            // 選擇i位置預(yù)約時間
            f[i] = g[i-1] + nums[i];
            // 不選擇i位置預(yù)約時間
            g[i] = Math.max(g[i-1],f[i-1]);
        } 
        // 4.返回值
        return Math.max(f[n-1],g[n-1]);
    }
}

以上就是接這道例題的整體思路。

其實(shí)也可以只創(chuàng)建一個dp表來求解這個問題，但是需要注意的是：一定要區(qū)分不同的狀態(tài)，也就是每個位置選擇或者不選擇。以下是解法，需要的老鐵可以結(jié)合注釋來理解：

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0; 
        // 1.創(chuàng)建dp 表
        // 多開兩個位置
        int[] dp = new int[n+2];
        // 2.初始化
        // 不同初始化
        // 3.填表
        // 從第2個下標(biāo)開始，從左到右
        for (int i = 2; i < n+2;i++) {
            // 先選擇當(dāng)前i位置的預(yù)約時間（由于多開了兩個位置，注意原來nums數(shù)組的映射）
            // 選擇了當(dāng)前i位置，則i-1位置就不能選擇了,則i-2位置可以選
            dp[i] = dp[i-2] + nums[i-2];
            // 不選當(dāng)前i位置的預(yù)約時間，和上面的值求個最大值就是當(dāng)前dp[i]的最終值
            dp[i] = Math.max(dp[i-1],dp[i]);
        }
        return dp[n+1];
    }
}

3.子數(shù)組系列問題?

上例題：53. 最大子數(shù)組和 - 力扣（LeetCode）

?接下來，使用五步法來解決這道例題：

1.狀態(tài)表示

先根據(jù)題目分析：首先，需要清楚什么是子數(shù)組，題目中已經(jīng)告訴我們，子數(shù)組是數(shù)組中的一個“連續(xù)”部分，也就是說，選取的一些元素，這些元素的下標(biāo)是連續(xù)的，在實(shí)例1中可以看出，從4開始到1的這部分子數(shù)組的和是最大的，其余的都比其小。

分析完題目，找狀態(tài)表示(dp[i])，dp[i] 表示的是dp表中每個位置的值代表的含義，在這道題中，需要找出整個數(shù)組中所有連續(xù)子數(shù)組中的最大和，因此，dp[i] 表示：以i位置元素結(jié)尾的所有連續(xù)子數(shù)組中最大的和。

2.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程就是找dp[i] 等于什么，如下圖：

要求dp[i] 就是找，以dp[i] 結(jié)尾的所有連續(xù)子數(shù)組中的最大和，對于以i位置結(jié)尾的所有連續(xù)自子數(shù)組，有如下這些（也就是i下標(biāo)元素和之前的元素組合，但是要求必須是連續(xù)的）：

也就是在這些所有連續(xù)子數(shù)組中找到和最大的。

對于上述子數(shù)組來說，可以劃分成兩種：一種是長度為1，也就是i位置元素自己，一種是長度大于1，也就是i位置元素和以i-1位置為結(jié)尾的連續(xù)子數(shù)組的最大和（也就是dp[i-1]）進(jìn)行相加。對于這兩種情況求最大值即可。

綜上，dp[i] = Math.max(nums[i],nums[i] + dp[i-1])

3.初始化

進(jìn)行初始化的時候，需要結(jié)合狀態(tài)轉(zhuǎn)移方程，在狀態(tài)轉(zhuǎn)移方程中出現(xiàn)了 i-1 ，此時就可以通過多開一個空間來避免越界，假設(shè)原來需要開辟的總長度是4，現(xiàn)在開辟5個空間，為了避免越界，填表的時候，從下標(biāo)為1的位置開始填即可，新增的第一個位置的值為0即可，這樣對后續(xù)填表就無影響。

由于多開了一個空間，需要注意和原數(shù)組的下標(biāo)映射關(guān)系。

4.填表順序

如果要求以4結(jié)尾的所有連續(xù)子數(shù)組的最大和，就需要知道以3結(jié)尾的連續(xù)子數(shù)組的最大和，因此，填表順序就是：從左到右

5.返回值

這道題目最終的返回值是整個數(shù)組中所有連續(xù)子數(shù)組的最大和，dp表中存的是以某個位置為結(jié)尾的所有連續(xù)子數(shù)組的最大和，因此，可能最大值是在dp表中間存著，也可能是在開頭或者結(jié)尾...? 所以，最后遍歷一次dp表（或者在填表的時候記錄最大值最終返回）即可得到最終結(jié)果。

上述就是整個解決此道動態(tài)規(guī)劃的分析流程，編寫代碼如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        // 1.創(chuàng)建dp表
        // 多開1個空間
        int[] dp = new int[n+1];
        // 2.初始化
        // 無需初始化
        // 3.填表
        // 從左到右，從1下標(biāo)開始填（注意下標(biāo)映射）
        for (int i = 1; i <= n;i++) {
            dp[i] = Math.max(nums[i-1],dp[i-1] + nums[i-1]);
        }
        // 4.返回值
        // 需要遍歷dp表,還是從1下標(biāo)開始
        int ret = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++) {
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}

以上就是子數(shù)組系列問題一道比較經(jīng)典的例題解法。

4.子序列問題

子序列問題也是比較經(jīng)典的動態(tài)規(guī)劃題型，這里需要區(qū)分子序列和子數(shù)組的，組成子序列的一些元素的下標(biāo)是可以不連續(xù)的，而組成子數(shù)組的一些元素的下標(biāo)要求是連續(xù)的。??

例題：300. 最長遞增子序列 - 力扣（LeetCode）

1.狀態(tài)表示

“經(jīng)驗(yàn) + 題目要求”

根據(jù)題目分析問題：要求找到給定數(shù)組中“最長嚴(yán)格遞增子序列的長度”，也就是找到所有遞增子序列中最長的長度。那么，dp表中就存的是：以某個位置為結(jié)尾的所有子序列中，最長遞增子序列的長度，所以，狀態(tài)表示（dp[i]）:以i位置結(jié)尾的所有子序列中，最長遞增子序列長度。

2.狀態(tài)轉(zhuǎn)移方程

“找dp[i] 等于什么”

對于子序列問題，處理方式和子數(shù)組問題相似，都是以 i 位置為結(jié)尾分情況討論：

i 位置自己的長度為1是一種情況，讓 i 位置元素跟在 [0,i-1] 這個區(qū)間內(nèi)的子序列的后面又是一種情況，因此dp[i] 就有兩種情況：

對于長度大于1這種情況，有一個前提：

必須保證 i 位置選擇要比前面的子序列的值要大。假設(shè) j 是[0,i-1] 區(qū)間某個下標(biāo)(0 <= j <= i-1)，那么想要 i 位置的元素跟在 j 位置的元素后面，就要求 nums[j] < nums[i]。由于[0,i-1] 這個范圍內(nèi)有很多個遞增子序列，因此，需要找到dp[j] 的最大值，然后 +1，得到dp[i]的值。

根據(jù)上述情況可以分析出有兩層循環(huán)，最外層需要記錄當(dāng)前是哪個位置i，最里面的循環(huán)需要記錄[0,i-1] 這個范圍內(nèi)的位置，然后每次更新dp[i]為最大值。

因此，狀態(tài)轉(zhuǎn)移方程為： dp[i] = Math.max(dp[i],dp[j] + 1)

3.初始化

“為了避免越界”。

對于這道題來說，在創(chuàng)建dp表的時候，將里面的長度全部更新為1，填表的時候，從1下標(biāo)開始填，這樣就可以很好的避免越界，并且可以直接表示dp[i] 長度為1這種情況。創(chuàng)建的dp表的規(guī)模是和原數(shù)組一樣大的。

4.填表順序

顯而易見，填表順序是：從左往右

5.返回值

由于dp表中每個位置記錄的都是以當(dāng)前位置為結(jié)尾的所有子序列中，最長遞增子序列的長度，所以，需要遍歷dp表來找到最大值，最后返回即可。

上述就是整個解決此道動態(tài)規(guī)劃的分析流程，編寫代碼如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        // 1.創(chuàng)建dp表
        // n規(guī)模大小的即可
        int[] dp = new int[n];
        // 2.初始化
        // 全部初始化為1
        Arrays.fill(dp,1);
        // 3.填表
        // 從左往右，下標(biāo)為1開始填
        for (int i = 1; i < n;i++) {
            // 遍歷[0,i-1]這個范圍 找到最大值+1和dp[i]進(jìn)行比較 
            for (int j = 0; j < i;j++) {
               // 必須要有這個前提
               if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
               }
            }
        }
        // 4.返回值
        // 遍歷一遍dp表，找到最大值
        int ret = 0;
        for (int i = 0; i < n;i++) {
            ret = Math.max(dp[i],ret);
        }
        return ret;
    }
}

以上就是子序列問題一道比較經(jīng)典的例題解法。

小技巧 √ ：

遇到子序列的問題，分析狀態(tài)轉(zhuǎn)移方程的時候，一般是分為長度為1（自己）和長度大于1（0~i-1和i組合的多種情況的最大值）兩種情況

5.回文串問題

例題：LCR 020. 回文子串 - 力扣（LeetCode）647. 回文子串 - 力扣（LeetCode）LCR 020. 回文子串 - 力扣（LeetCode）

?1.狀態(tài)表示

根據(jù)題目分析：首先要明確什么是回文字符串。使用動態(tài)規(guī)劃來解決回文子串問題，需要保證能將所有的子串是否是回文的信息保存在dp表中，可以通過兩層for循環(huán)來表示某個字符串的所有子串，i 位置表示起始位置，j 表示結(jié)尾位置，i ~ j 這個區(qū)間就是子字符串，因此，可以看出，再創(chuàng)建dp表的時候就可以創(chuàng)建一個二維的dp表。假設(shè)如下圖是創(chuàng)建出的dp表：

讓 i 表示起點(diǎn)，j 表示結(jié)尾，[0,0] 表示以0下標(biāo)開始，以0下標(biāo)結(jié)尾，[0,1] 表示以0開始，以1結(jié)尾，[0,2] 表示以0開始，以2結(jié)尾。[1,0] 表示以1開始，以0結(jié)尾，這種情況其實(shí)已經(jīng)記錄過了，就是[0,1] 這種情況，因此，dp表的主對角線下方數(shù)據(jù)都不用填，只需要填主對角線及其上方的。

dp 表中記錄的是子串是否是回文的信息，因此就可以推導(dǎo)出狀態(tài)表示(dp[i,j]) : s 字符串[i,j] 的子串，是否是回文串。

2.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程就是找dp[i,j] 等于什么，對于這道題而言，[i,j] 表示的是這個區(qū)間的子字符串是不是回文字符串，因此dp表是一個boolean類型的二維數(shù)組，想要知道一個區(qū)間的字符串是不是回文字符串，首先判斷i 和 j 位置的字符是不是相等，根據(jù)是否相等劃分出兩種情況：

當(dāng)s[i] !=s[j] 時，dp[i,j] = false，當(dāng)s[i] == s[j] 時，又根據(jù)i 和 j 的位置劃分出三種不同的情況，當(dāng) i == j (指向同一個字符)或者 i+1 = j 時，dp[i,j] = true, 最后一種情況是:[i,j] 這個區(qū)間有很多個字符，此時就需要根據(jù)[i+1,j-1] 這個區(qū)間的boolean值來判斷[i,j] 這個區(qū)間是不是回文串。

以上就是狀態(tài)轉(zhuǎn)移方程的分析過程。

3.初始化

避免填表的時候越界，根據(jù)狀態(tài)轉(zhuǎn)移方程來進(jìn)行初始化，在狀態(tài)轉(zhuǎn)移方程中出現(xiàn)了 i+1 和 j-1可能越界，在第一步的時候已經(jīng)說過，dp表中用到的數(shù)據(jù)都是主對角線及其上面的部分，因此i <= j，但是當(dāng) i == j 這種特殊情況已經(jīng)特殊處理了，因此就不用初始化。

4.填表順序

假設(shè)要填dp[2,5]，根據(jù)狀態(tài)轉(zhuǎn)移方程，需要保證dp[3,4] 已經(jīng)填過了，所以填表順序是從下往上填。

5.返回值

由于dp表中存的是所有子串是不是回文，因此，就可以找dp表中true的數(shù)量來得到回文串的數(shù)量，所以，返回值就是dp表中true的個數(shù)。

上述就是整個解決此道動態(tài)規(guī)劃的分析流程，編寫代碼如下：

class Solution {
    public int countSubstrings(String ss) {
        int n = ss.length();
        if (n == 0) return 0;
        char[] s = ss.toCharArray();
        // 1.創(chuàng)建dp表
        boolean[][] dp = new boolean[n][n];
        //2.初始化
        // 無需初始化
        // 3.填表，從下往上填
        // 最外層確定起點(diǎn)
        for (int i = n-1; i >= 0;i--) {
            // 最里層確定重點(diǎn)
            for (int j = i; j < n;j++) {
                if (s[i] == s[j]) {
                    if (i == j || i+1 == j) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                } 
            }
        }
        // 4.返回值
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0; j < n;j++) {
                if (dp[i][j]) {
                    ret++;
                }
            }
        }
        return ret;
    }
}

以上就是回文串問題一道比較經(jīng)典的例題解法。

接下來兩道例題都是背包問題比較經(jīng)典的動態(tài)規(guī)劃問題，在介紹之前補(bǔ)充一下什么是背包問題：

背包問題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。

根據(jù)給定物品的個數(shù)，可以分為如下幾類：

01背包問題：每個物品只有一個

完全背包問題：每個物品有無限多個

........

背包問題如下圖：

6.01背包問題

?對于01背包來說，每個物品的數(shù)量都是固定的，只有一個。

例題：【模板】01背包_?？皖}霸_?？途W(wǎng) (nowcoder.com)

?先分析題目：第一問實(shí)際上就是在問不必裝滿背包時，可以獲得的最大價(jià)值。先來解決第一問，背包不必裝滿的情況。依舊是使用解決動態(tài)規(guī)劃問題的五步：

1.狀態(tài)表示

根據(jù)經(jīng)驗(yàn)+題目要求來分析：題目要求最終要返回最大價(jià)值，因此dp表中需要存已挑選出的物品的最大價(jià)值，由此可以得出：dp[i] 表示從前 i 個物品中選，所有選法中，能挑選出來的最大價(jià)值。先來思考一下，這個狀態(tài)轉(zhuǎn)移方程是否正確？ 顯而易見，不正確，因?yàn)檫@個dp表無法保證背包的容量是多少，不知道什么時候裝滿或者超過容量，因此，dp表還需要記錄當(dāng)前背包的容量，所以，將這個dp表創(chuàng)建成一個二維數(shù)組，橫坐標(biāo)表示物品的編號，縱坐標(biāo)表示背包的容量。因此：dp[i][j] 表示：從前 i 個物品中挑選，總體積不超過 j，所有選法中，能挑選出來的最大價(jià)值。

2.狀態(tài)轉(zhuǎn)移方程

找dp[i][j] 等于什么。

對于每個位置的物品來說，都有自己的體積和價(jià)值，并且該物品有兩種選擇，選或者不選，因此，如果不選擇 i 位置的物品，那么dp[i][j] 的最大價(jià)值就是前 i -1個物品所有選法，體積不超過 j 的最大價(jià)值，也就是 dp[i][j] = dp[i-1][j]; 如果選擇 i 位置的物品,w[i] 表示 i 物品的價(jià)值，v[i] 表示 i 物品的體積，dp[i][j] = w[i] + dp[i-1][j-v[i]] (w[i] 是i物品的價(jià)值，選擇 i 物品的話，就加上 i 的價(jià)值，dp[i-1][j-v[i]] 表示 前 i -1 個物品中挑選，總體積不超過 j - v[i]，所有選法中的最大價(jià)值，因?yàn)?i 物品要選擇，所以要保證從前往后選擇物品時，有空間裝下v[i],因此，從前 i-1 個物品中挑選時，體積不超過 j-v[i] 這樣就保證一定能裝下v[i],但是需要注意，j - v[i] >=0,必須確保能夠裝下i物品?)。

綜上,選擇兩種選法中的最大值，dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]] + w[i])

3.初始化

根據(jù)狀態(tài)轉(zhuǎn)移方程來初始化，避免填表越界。

物品編號是從 1 開始，創(chuàng)建dp表時多開一行和一列，假設(shè)給的物品種類是3，背包容量是4，那么創(chuàng)建出的dp表就是dp[4][5]:

第一行表示：從前0個物品中挑選，體積不超過j，不選物品，那么最大價(jià)值就是0，因此第一行都是0。

第一列表示：從前i個物品中挑選，體積不超過0，每個物品都是有體積的，所有沒有選法，因此第一列都是0。

狀態(tài)轉(zhuǎn)移方程出現(xiàn)了i -1，但是第一行和第一列都是0，不必初始化，從第二行開始填，就可以避免越界。由于物品下標(biāo)是從1開始的，對應(yīng)到物品的價(jià)值數(shù)組w 和 物品的體積數(shù)組v時，需要注意下標(biāo)映射。

4.填表順序

填dp[i][j] 時，依賴前一個位置dp[i-1][j] 以及左上方位置dp[i-1][j-v[i]]，因此，填表順序是：

從上往下。

5.返回值

在第一問中，題目要求返回的是：n個物品，總體積不超過v，所有選法中的最大價(jià)值，返回dp[n][v]即可。

以上就是01背包的第一問解題思路。

接下來解決第二問，第二問題目要求剛好裝滿背包，此時的最大價(jià)值

?1.狀態(tài)表示

狀態(tài)表示分析過程和第一問的相似，直接得出結(jié)論：

dp[i][j]表示：從前 i 個物品中挑選，體積剛好等于 j，所有選法中，能挑選出來的最大價(jià)值。

2.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程與第一問的一樣，但是有幾個小細(xì)節(jié)。

首先，如果不選擇 i 物品的話，此時dp[i][j] = dp[i-1][j], 但是，可能不選擇i物品且剛好從i-1個物品中挑選出體積 j 這種情況不存在，因此，將dp表中的一些值設(shè)置成 -1 ,表示當(dāng)前這種情況不存在。 不選擇 i 物品的話，需要保證 dp[i-1][j] != -1,但是，可以直接讓dp[i][j] = dp[i-1][j],即使此時這種情況不存在，也無所謂，因?yàn)閐p[i][j] 也不存在。

其次，如果選擇 i 物品的話，此時就要再加一個條件,和之前一樣先要保證有足夠背包空間裝當(dāng)前 i 物品的體積，也就是 j -v[i] >= 0,另一個條件就是：必須保證從前 i - 1 個物品中挑選的時候，dp[i-1][j-v[i]] 這種情況存在，也就是 dp[i-1][j-v[i]] != -1。

然后從上述兩種情況取最大值：dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]] + w[i])

3.初始化

此時的初始化，由于dp表中要存 -1這種情況，因此，重新分析：

還是多開一行和一列來避免越界，此時要考慮多開的這一行和這一列的初始值。

對于第一行來說，當(dāng) i 為0時，想要前0個物品中挑選出體積為j，這種情況顯然不可能，因此第一行除了dp[0][0] 其余的值均為 -1。

對于第一列來說，當(dāng) j 為0時，想要前 i 個物品中挑選出體積為0，這種情況不選即可，dp[i][0] 均為0.

如下圖:

4.填表順序

和第一問一樣：從左到右

5.返回值

和第一問一樣，最終返回結(jié)果應(yīng)該是dp[n][v],但是需要注意，對于背包恰好裝滿這種情況，可能不存在，所以需要判斷最終結(jié)果是不是等于 -1,然后再進(jìn)行返回。

以上就是所有分析流程，詳細(xì)代碼如下：

import java.util.Scanner;

// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的區(qū)別
        while (in.hasNextInt()) { // 注意 while 處理多個 case
            int n = in.nextInt(); // 物品數(shù)量
            int V = in.nextInt(); // 背包體積
            int[] v = new int[n]; // 物品體積數(shù)組
            int[] w = new int[n]; // 物品價(jià)值數(shù)組
            for (int i = 0; i < n; i++) {
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }
            // 第一問結(jié)果
            int ret1 = func1(n, V, v, w);
            // 第二問結(jié)果
            int ret2 = func2(n, V, v, w);
            System.out.println(ret1);
            System.out.println(ret2);

        }
    }
    // 第一問
    public static int func1(int n, int V, int[] v, int[] w) {
        // 1.創(chuàng)建dp表
        int[][] dp = new int[n + 1][V + 1];
        // 2.初始化
        // 無需初始化
        // 3.填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                // 不選當(dāng)前物品
                dp[i][j] = dp[i - 1][j];
                // 如果體積可以裝當(dāng)前物品，那么選當(dāng)前物品 然后求最大值
                // 注意下標(biāo)映射
                if (j - v[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
        // 4.返回值
        return dp[n][V];
    }
    // 第二問
    public static int func2(int n, int V, int[] v, int[] w) {
        // 1.創(chuàng)建dp表
        int[][] dp = new int[n + 1][V + 1];
        // 2.初始化
        // 第一行后續(xù)都為-1
        for (int j = 1; j <= V;j++) {
            dp[0][j] = -1;
        }
        // 3.填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                // 不選當(dāng)前物品
                dp[i][j] = dp[i - 1][j];
                // 如果體積可以裝當(dāng)前物品并且dp[i-1][j-v[i]]這種情況存在，那么選當(dāng)前物品 然后求最大值
                // 注意下標(biāo)映射
                if (j - v[i - 1] >= 0 && dp[i-1][j-v[i-1]] != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
        // 4.返回值
        return dp[n][V] == -1?0:dp[n][V];
    }
}

7.完全背包

?對于完全背包來說，每個物品的數(shù)量都是無窮的。?

?例題：【模板】完全背包_?？皖}霸_?？途W(wǎng) (nowcoder.com)

該題目與01背包問題幾乎相同，只是物品數(shù)量不同，因此，對題目的分析和上述基本類似，此處不過多贅述，先來求解第一問。

1.狀態(tài)表示

和01背包的狀態(tài)表示相同：

dp[i][j] 表示：從前 i 個物品中挑選，總體積不超過 j，所有選法中，能挑選出來的最大價(jià)值。

2.狀態(tài)轉(zhuǎn)移方程

對于01背包來說，由于物品只有一個，因此每個物品只有選和不選兩種情況，但是完全對于完全背包而言，由于物品個數(shù)有無窮個，因此，每個物品有很多種選擇，包括不選、選一個、選兩個、選三個...... 對于不選當(dāng)前物品來說，其狀態(tài)轉(zhuǎn)移方程dp[i][j] = dp[i-1][j]，對于選1個物品來說，其狀態(tài)轉(zhuǎn)移方程dp[i][j] = dp[i-1][j-v[i]] + w[i],也就是01背包的另一個狀態(tài)轉(zhuǎn)移方程，對于選2個物品來說，其狀態(tài)轉(zhuǎn)移方程dp[i][j] = dp[i-1][j-2v[i]] + 2w[i](也就是當(dāng)前 i 物品選兩次，其價(jià)值就是2w[i],然后從前面i-1個物品中挑選，體積不超過j-2v[i]),對于選3個物品來說，其狀態(tài)轉(zhuǎn)移方程dp[i][j] = dp[i-1][j-3v[i]] + 3w[i]......?

對于dp[i][j] 而言，是從上面的所有情況中找最大值，因此：

上圖就是狀態(tài)轉(zhuǎn)移方程的推導(dǎo)過程。

3.初始化

根據(jù)狀態(tài)轉(zhuǎn)移方程來初始化，避免填表越界。

物品編號是從 1 開始，創(chuàng)建dp表時多開一行和一列，假設(shè)給的物品種類是3，背包容量是4，那么創(chuàng)建出的dp表就是dp[4][5]:

第一行表示：從前0個物品中挑選，體積不超過j，不選物品，那么最大價(jià)值就是0，因此第一行都是0。

第一列表示：從前i個物品中挑選，體積不超過0，每個物品都是有體積的，所有沒有選法，因此第一列都是0。

狀態(tài)轉(zhuǎn)移方程出現(xiàn)了i -1，但是第一行和第一列都是0，不必初始化，從第二行開始填，就可以避免越界。由于物品下標(biāo)是從1開始的，對應(yīng)到物品的價(jià)值數(shù)組w 和 物品的體積數(shù)組v時，需要注意下標(biāo)映射。

對于dp[i-1][j-v[i]]+w[i],這種情況來說，可能會存在j-v[i] 不存在，也就是 j-v[i] < 0,因此，在使用的時候需要注意判斷。

4.填表順序

想要填dp[i][j] 位置，依賴dp[i-1][j],說明從上往下填，又依賴dp[i][j-v[i]] + w[i],說明只能從左往右填，綜上，填表順序：從上往下并且從左到右

5.返回值

第一問題目要求背包最多能裝下的最大價(jià)值，因此，返回dp[n][v]

以上就是01背包的第一問解題思路。

接下來解決第二問，第二問題目要求剛好裝滿背包，此時的最大價(jià)值

?1.狀態(tài)表示

狀態(tài)表示分析過程和第一問的相似，直接得出結(jié)論：

dp[i][j]表示：從前 i 個物品中挑選，體積剛好等于 j，所有選法中，能挑選出來的最大價(jià)值

2.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程與第一問的一樣：dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i])

但是有幾個小細(xì)節(jié)。

首先，如果不選擇 i 物品的話，此時dp[i][j] = dp[i-1][j], 但是，可能不選擇i物品且剛好從i-1個物品中挑選出體積 j 這種情況不存在，因此，將dp表中的一些值設(shè)置成 -1 ,表示當(dāng)前這種情況不存在。 不選擇 i 物品的話，需要保證 dp[i-1][j] != -1,但是，可以直接讓dp[i][j] = dp[i-1][j],即使此時這種情況不存在，也無所謂，因?yàn)閐p[i][j] 也不存在。

其次，如果選擇 i 物品(1個、2個、3個......)的話，此時就要再加一個條件,和之前一樣先要保證有足夠背包空間裝當(dāng)前 i 物品的體積，也就是 j -v[i] >= 0,另一個條件就是：必須保證

dp[i][j-v[i]] 這種情況存在，也就是 dp[i][j-v[i]] != -1。

3.初始化

?此時的初始化，由于dp表中要存 -1這種情況，因此，重新分析：

還是多開一行和一列來避免越界，此時要考慮多開的這一行和這一列的初始值。

對于第一行來說，當(dāng) i 為0時，想要前0個物品中挑選出體積為j，這種情況顯然不可能，因此第一行除了dp[0][0] 其余的值均為 -1。

對于第一列來說，當(dāng) j 為0時，想要前 i 個物品中挑選出體積為0，這種情況不選即可，dp[i][0] 均為0.

如下圖:

4.填表順序

和第一問相同，從上到下并且從左到右

5.返回值

在返回之前，需要判斷dp[n][v] 這種情況是否存在，因?yàn)閷τ诒嘲『醚b滿這種情況可能不存在。

以上就是所有分析流程，詳細(xì)代碼如下：

import java.util.Scanner;

// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的區(qū)別
        while (in.hasNextInt()) { // 注意 while 處理多個 case
            int n = in.nextInt();// 物品個數(shù)
            int bagV = in.nextInt();// 背包體積
            int[] v = new int[n];// 物品體積
            int[] w = new int[n];// 物品價(jià)值
            for (int i = 0; i < n; i++) {
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }
            // 第一問
            int ret1 = func1(n, bagV, v, w);
            System.out.println(ret1);
            // 第二問
            int ret2 = func2(n, bagV, v, w);
            System.out.println(ret2);
        }
    }
    // 第一問
    public static int func1(int n, int bagV, int[] v, int[] w) {
        // 1.創(chuàng)建dp表
        //多開一行一列
        int[][] dp = new int[n + 1][bagV + 1];
        // 2.初始化
        // 不用初始化
        // 3.填表
        // 從上往下并且從左到右
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= bagV; j++) {
                // 不選該物品
                dp[i][j] = dp[i - 1][j];
                // 和另外的狀態(tài)轉(zhuǎn)移方程對于求最大值
                // 注意下標(biāo)映射
                if (j - v[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
        // 4.返回值
        return dp[n][bagV];
    }
    // 第二問
    public static int func2(int n, int bagV, int[] v, int[] w) {
        // 1.創(chuàng)建dp表
        //多開一行一列
        int[][] dp = new int[n + 1][bagV + 1];
        // 2.初始化
        for (int j = 1;j <= bagV;j++) {
            dp[0][j] = -1;
        }
        // 3.填表
        // 從上往下并且從左到右
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= bagV; j++) {
                // 不選該物品
                dp[i][j] = dp[i - 1][j];
                // 和另外的狀態(tài)轉(zhuǎn)移方程對于求最大值
                // 注意下標(biāo)映射
                if (j - v[i - 1] >= 0 && dp[i][j-v[i-1]] != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
        // 4.返回值
        // 返回之前判斷是否可以裝滿
        return dp[n][bagV] == -1?0:dp[n][bagV];
    }
}

?以上就是動態(tài)規(guī)劃問題的一些相關(guān)例題。文章來源地址http://www.zghlxwxcb.cn/news/detail-788617.html

到了這里，關(guān)于動態(tài)規(guī)劃：解決復(fù)雜問題的魔法武器的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！