動態(tài)規(guī)劃（Dynamic Programming）

動態(tài)規(guī)劃，簡稱DP，它是求解最優(yōu)化問題的一種常見策略。例如前面章節(jié)中提到的找零錢問題，要求找的硬幣個數(shù)最少；或者最大連續(xù)子序列和問題。所以，很多時候，有帶最子的問題，都可以使用動態(tài)規(guī)劃的方式來解決。

動態(tài)規(guī)劃的使用套路：一步一步進行優(yōu)化。也就是說，當對動態(tài)規(guī)劃不夠熟悉時，可能并不能直接就能想到使用動態(tài)規(guī)劃的解法來解決一個問題，很有可能是一步一步進行優(yōu)化，例如進行如下的方式

1. 暴力遞歸（自頂向下，出現(xiàn)了重疊子問題）
2. 記憶化搜索（自頂向下）
3. 遞推（自底向上）

另外，動態(tài)規(guī)劃還有其他的基本理論，這里先不著急進行介紹。先通過一個示例場景問題，對動態(tài)規(guī)劃有一個初步的了解。

場景一：找零錢[LeetCode]

假設有25分，20分，5分，1分的硬幣，現(xiàn)在要找給客戶41分零錢，如何辦到硬幣個數(shù)最少

在前面，這個問題曾經使用過貪心策略來進行求解，但是并沒有得到最優(yōu)解（貪心得到的解是5枚），但是使用動態(tài)規(guī)劃來解決這個問題的話，就能得到最優(yōu)解。

使用動態(tài)規(guī)劃解該問題，其中假設dp(n)是湊到n分需要的最少硬幣數(shù)量，存在以下幾種情況：

• 如果第一次選擇了25分的硬幣，那么dp(n) = dp(n - 25) + 1;
• 如果第一次選擇了20分的硬幣，那么dp(n) = dp(n - 20) + 1;
• 如果第一次選擇了5分的硬幣，那么dp(n) = dp(n - 5) + 1;
• 如果第一次選擇了1分的硬幣，那么dp(n) = dp(n - 1) + 1;

所以現(xiàn)在dp(n)存在以上4中情況

那么，最小dp(n)的值為 dp(n) = min{dp(n - 25),dp(n - 20),dp(n - 5),dp(n - 1)} +1，也就是說從dp(n - 25),dp(n - 20),dp(n - 5),dp(n - 1)4中情況中選出硬幣數(shù)量最少的一種，就是dp(n)硬幣數(shù)量最少的情況

所以，現(xiàn)在相當于把dp(n)的所有情況都考慮到了。

通過上面的分析，最終得到的代碼如下

static int coins(int n) {
    if (n < 1) return Integer.MAX_VALUE;
    if (n == 25 || n == 20 || n == 5 || n ==1) return 1;
    int min1 = Math.min(coins(n - 25),coins(n - 20));
    int min2 = Math.min(coins(n - 5),coins(n - 1));
    return Math.min(min1,min2) + 1;
}

通過，這種方法，再次對41分零錢進行求解的話，最終得到的結果為3枚。是最終想要的結果

代碼優(yōu)化

仔細觀察可以發(fā)現(xiàn)，上面這種計算硬幣最少數(shù)量的解法，與前面介紹的斐波那鍥數(shù)列的解法非常相似，存在非常多的重復計算問題，所以可以使用記憶搜索來進行優(yōu)化，即計算過的值，進行記錄后面直接使用，不在計算，所以，通過優(yōu)化，得到代碼如下

static int coins(int n) {
    if (n < 1) return -1;
    int[] dp = new int[n + 1];
    int[] faces = {1,5,20,25};
    for (int face : faces) {
        if (n < face) break;
        dp[face] = 1;
    }
    dp[1] = dp[5] = dp[20] = dp[25] = 1;
    return coins(n,dp);
}
static int coins(int n, int[] dp) {
    if (n < 1)return Integer.MAX_VALUE;
    if (dp[n] == 0) {
        int min1 = Math.min(coins(n - 25,dp),coins(n - 20,dp));
        int min2 = Math.min(coins(n - 5,dp),coins(n - 1,dp));
        dp[n] = Math.min(min1,min2) + 1;
    }
    return dp[n];
}

這種優(yōu)化方式依然是采用自頂向下的方式來計算的，并且依然是遞歸調用， 所以還存在?？臻g的開銷，所以現(xiàn)在可以考慮采用另外的方式進行優(yōu)化，結合前面的介紹，使用記憶化搜索以后，可以使用遞推的方式來進行進行的優(yōu)化，所以接下來使用遞推的方式來進行優(yōu)化

遞推

遞推采用的是自底向上的方式 來進行計算的。所以可以將上面的代碼修改為如下方式

static int coins(int n){
    if (n < 1) return -1;
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE
            
            ;
        if (i >= 1) min = Math.min(dp[i - 1], min);
        if (i >= 5) min = Math.min(dp[i - 5], min);
        if (i >= 20) min = Math.min(dp[i - 20], min);
        if (i >= 25) min = Math.min(dp[i - 25], min);
        dp[i] = min + 1;
    }
    return dp[n];
}

通過遞推的方式來進行求解的話，其時間復雜度與空間復雜度均為O(n)

現(xiàn)在，通過遞推的方式，將上面求解的代碼進行整合，變得更加通用，結果如下

static int generalCoins(int n,int[] faces){
    if (n < 1 || faces == null || faces.length == 0) return -1;
    int [] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        for (int face : faces) {
            if (i < face) continue;
            min = Math.min(dp[i - face],min);
        }
        dp[i] = min + 1;
    }
    return dp[n];
}

為什么這種解法，叫做動態(tài)規(guī)劃？

現(xiàn)在來回顧一下解決該問題，經過的步驟。

1. 暴力遞歸
2. 記憶化搜索
3. 遞推

所以，在最開始的時候，是使用暴力遞歸的方式，來對問題進行求解，對計算找n分零錢，最少需要多少枚硬幣，轉換為計算n - 1, n - 5 , n - 20, n - 25,這4中情況中中最少的一種情況再+1，就是找n分零錢最少的硬幣數(shù)量。

后來，發(fā)現(xiàn)在進行暴力遞歸時，有很多重復的計算，所以就將暴力遞歸的方式進行了優(yōu)化，改為了記憶化搜索的方式，記錄某一面值，需要硬幣數(shù)量的情況。但是記憶化搜索僅僅是解決了重復計算的問題， 它依然是自上而下的一種調用方式，并沒有解決遞歸調用，消耗棧空間的問題。

最終，經過進一步的觀察，發(fā)現(xiàn)可以將自頂向下的方式改為自底向上地方方式來進行計算，通過計算出較小的值，然后利用較小的值推導出較大值的這種方式，這樣的話，就將遞歸調用給去掉了，所以最終的實現(xiàn)，就變?yōu)榱松厦孀詈蟮姆绞健?/p>

以上的整個過程，就可以理解為在執(zhí)行動態(tài)規(guī)劃的過程。結合上面的場景問題，接下來將對動態(tài)規(guī)劃的常規(guī)步驟進行研究。

動態(tài)規(guī)劃的常規(guī)步驟

動態(tài)規(guī)劃中的“動態(tài)”可以理解為“會變化的狀態(tài)”，其步驟如下

1. 定義狀態(tài)（何為狀態(tài)：狀態(tài)就是原問題，子問題的解）

   • 例如定義dp(i)的含義

     在解決零錢兌換問題時，就定義了dp(n)的含義，即湊到n分需要的硬幣個數(shù)，所以dp(41)就表示湊夠41分，需要的硬幣個數(shù)；dp(4)就問湊夠4分，需要的硬幣個數(shù)

     可以發(fā)現(xiàn)，定義的狀態(tài)中的dp(n)就位最終要得到的解，同時也是子問題的解

2. 設置邊界條件（邊界條件）

   • 例如設置一些可以確定的值

     在解決零錢兌換問題是，就定義了dp(1),dp(5),dp(20),dp(25)的值，這些值都是可以直接確定的

     確定了初始狀態(tài)以后，就可以進行下一步了

3. 確定狀態(tài)轉移方程

   • 比如確定dp(i)與dp(i - 1)之間的關系(利用舊的狀態(tài)，推導出新的狀態(tài)，比如現(xiàn)一直dp(i - 1)的值，利用dp(i - 1)推導出dp(i)的值)

動態(tài)規(guī)劃的相關概念

來自維基百科的解釋

動態(tài)規(guī)劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。

根據上面的解釋，可以得到以下結論

1. 將復雜的原問題，拆解成若干個簡單的子問題
2. 每個子問題僅僅解決一次，并保存它們的解
3. 最后推導出原問題的解

一般來講，若可以利用動態(tài)規(guī)劃來解決的問題，通常具備2個特點

1. 最優(yōu)子結構（最優(yōu)化原理）：通過求解子問題的最優(yōu)解，可以獲得原問題的最優(yōu)解

   • 上面的零錢兌換，是滿足這個條件的

2. 無后效性（也就意味著，該問題僅僅擁有最優(yōu)子機構是不夠的，還需要有無后效性）

   • 即某階段的狀態(tài)一旦確定，則此后過程的演變，不會受到此前各狀態(tài)及決策的影響（未來與過去無關）

     例如，在零錢兌換時，是通過零錢比較少的狀態(tài)，推導出零錢比較多的狀態(tài)。在零錢少時確定的狀態(tài)，并不會隨著后面零錢邊多后，最終的結果發(fā)生變化，而且后面零錢變多后的推導過程，也不會受前面零錢少時狀態(tài)的影響

   • 在推導后面階段的狀態(tài)時，只關心前面階段的具體狀態(tài)值，不關心這個狀態(tài)是怎么一步步推導出來的

     在零錢兌換時，兌換dp(41)的零錢，只關心dp(40),dp(36),dp(16),dp(21)的值是多少，并不關心這些值是怎么計算出來的

無后效性舉例

現(xiàn)在有如下圖所示的5*5格子

現(xiàn)在要從起點(0,0)走到終點(4,4)，要計算一共有多少種走法（規(guī)定只能往右，往下走）

利用動態(tài)規(guī)劃來解決的話，首先第一步是定義狀態(tài)，定義狀態(tài)如下

假設dp(i,j)是從(0,0)走到(i,j)的走法

可以發(fā)現(xiàn)，定義的這個狀態(tài)，既是原問題的解，也是子問題的解

接下來設置邊界條件，如下所示

dp(i,0) = dp(0,j) = 1

確定好邊界條件以后，就可以設置狀態(tài)轉移方程了，通過規(guī)定可以知道，某個點dp(i,j)只可能從兩個方向走過來，一個是從dp(i - 1,j)向右走一步到達dp(i,j),或者是從dp(i,j-1)往下走一步，到達dp(i,j)，所以可以知道

dp(i,j) = dp(i - 1,j) + dp(i,j-1)

通過動態(tài)規(guī)劃的步驟，最終就可以算出到達(4,4)一共的走法。

在這里，無后效性體現(xiàn)在:

推導dp(i,j) =時，只需要用到dp(i - 1,j) 與 dp(i,j-1)的結果，并不需要關心dp(i - 1,j) 與 dp(i,j-1)的值是怎么計算出來的

有后效性舉例

現(xiàn)在同樣有如下的格子

要從起點(0,0)走到終點(4,4)，要計算一共有多少種走法。但是現(xiàn)在規(guī)定可以向左，向右，向上，向下走，并且同一格子不能走兩次

有后效性體現(xiàn)在

現(xiàn)在假設要走到(i,j)這個點，要推導出下一個點dp(i + 1,j) 或 dp(i,j+1)，由于規(guī)定同一個格子不能走兩次，所以前面格子的走法就決定了后面點的走法，才能保證下一步的走法不會導致同一個點走兩次

對動態(tài)規(guī)劃的概念和步驟有一定的了解以后，接下來利用一些場景問題，對動態(tài)規(guī)劃進行深入的理解。

場景二：最大連續(xù)子序列和

最大連續(xù)子序列和，這個問題，在分治策略部分章節(jié)曾有接觸過，當時是通過分治的方法來進行求解，分別計算左邊部分的最大連續(xù)子序列和/右邊部分的最大連續(xù)子序列和/左右種均存在的最大子序列和，在計算出這三個值中最大的值，這是采用分治策略的一種解法。雖然通過這種方法計算出了最終的結果，但是分治策略來計算并不是最優(yōu)的，接下來，就使用動態(tài)規(guī)劃的方式來計算。

給定一個長度為n的整數(shù)序列，求它的最大連續(xù)子序列和

• 比如-2,1,-3,4,-1,2,1,-5,4的最大連續(xù)子序列和是4 + (-1) + 2 + 1 = 6

定義狀態(tài)

采用動態(tài)規(guī)劃的方式來進行求解的話，首先要做的就是定義狀態(tài)dp(i),但是問題在于，dp(i)代表著什么含義呢？

在這里，期望得到的結果為計算出當前序列的最大連續(xù)子序列和。其實，等價于計算當前序列的最大連續(xù)子序列，只不過在計算出最大連續(xù)子序列以后，將這些序列的值加起來，就可以得到最大連續(xù)子序列了

但是，并不是任意一個子序列都是最終期望的解，所以可以先排除一些不必要的結果，也就是說，最大連續(xù)子序列可能是以序列中的某個元素結尾的序列，例如最大子序列可能為(1,-3)，則是以-3結尾的序列，也可能是(4,-1,2,1)，則是以1結尾的序列，也可能是(-1,2,1,-5)，則是以-5結尾的序列

通過上面的分析，可以先計算出以序列中元素結尾的最大子序列出來，然后再選擇這些最大子序列中，最大的序列，所以可以通過如下的方式來定義dp(i)的狀態(tài)

dp(i)是以nums[i]結尾的最大連續(xù)子序列和（nums是整個序列）

所以，結合上面的序列，可以得到以下的結論:

1. dp(0)表示以nums(0)結尾的最大連續(xù)子序列和，所以dp(0)的序列為（-2），那么要計算的序列就是以-2結尾的最大連續(xù)子序列，所以dp(0) = -2，最大子序列為（-2）
2. 以nums(1)結尾的最大連續(xù)子序列和，所以dp(1)的序列為（-2,1），那么要計算的序列就是以1結尾的最大連續(xù)子序列，所以dp(1) = 1，最大子序列為（1）
3. 以nums(2)結尾的最大連續(xù)子序列和，所以dp(2)的序列為（-2,1,-3），那么要計算的序列就是以-3結尾的最大連續(xù)子序列，所以dp(2) = -2(該序列必須包含-3，所以結果不能是1)，最大子序列為（1,-3）
4. 以nums(3)結尾的最大連續(xù)子序列和，所以dp(3)的序列為（-2,1,-3,4），那么要計算的序列就是以4結尾的最大連續(xù)子序列，所以dp(3) = 4，最大子序列為（4）
5. 以nums(4)結尾的最大連續(xù)子序列和，所以dp(4)的序列為（-2,1,-3,4,-1），那么要計算的序列就是以-1結尾的最大連續(xù)子序列，所以dp(4) = 3，最大子序列為（4,-1）
6. 以nums(5)結尾的最大連續(xù)子序列和，所以dp(5)的序列為（-2,1,-3,4,-1,2），那么要計算的序列就是以2結尾的最大連續(xù)子序列，所以dp(5) = 5，最大子序列為（4,-1,2）
7. 以nums(6)結尾的最大連續(xù)子序列和，所以dp(6)的序列為（-2,1,-3,4,-1,2,1），那么要計算的序列就是以1結尾的最大連續(xù)子序列，所以dp(6) = 6，最大子序列為（4,-1,2,1）
8. 以nums(7)結尾的最大連續(xù)子序列和，所以dp(7)的序列為（-2,1,-3,4,-1,2,1,-5），那么要計算的序列就是以-5結尾的最大連續(xù)子序列，所以dp(7) = 1，最大子序列為（4,-1,2,1,-5）
9. 以nums(8)結尾的最大連續(xù)子序列和，所以dp(8)的序列為（-2,1,-3,4,-1,2,1,-5,4），那么要計算的序列就是以4結尾的最大連續(xù)子序列，所以dp(8) = 5，最大子序列為（4,-1,2,1,-5,4）

這樣，就計算出了以每一個元素結尾的最大連續(xù)子序列和，最終要計算的整一個序列的最大連續(xù)子序列和，就是所有dp(i)中的最大值，即在本示例中的dp(0)至dp(8)的最大值，就為最終要得到的結果

規(guī)律：以nums(1)為例，要計算當前序列的最大連續(xù)子序列，就要參考前面的nums(0)的最大連續(xù)子序列的值，如果nums(0)的最大連續(xù)子序列和的結果小于等于0，那么nums(1)的最大連續(xù)子序列和就不需要加上nums(0)的值，所以，dp(i - 1) <= 0，那么dp(i)的值就位nums(i)，否則dp(i) = dp(i - 1) + nums(i)

通過以上的規(guī)律，則可以得到以下的狀態(tài)轉移方程

• 如果dp(i - 1) <= 0，那么dp(i) = nums(i)
• 如果dp(i - 1) > 0，那么dp(i) = dp(i - 1) + nums(i)

初始狀態(tài)dp(0)的值為nums(0)

最終，可以求的的解為：最大連續(xù)子序列和是所有dp(i)中的最大值max{dp(i)},i∈[0,nums.length)

實現(xiàn)代碼如下

static int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int max = dp[0];
    System.out.println("dp[0] = " + dp[0]);
    for (int i = 1; i < nums.length; i++) {
        if (dp[i - 1] < 0) {
            dp[i] = nums[i];
        } else {
            dp[i] = dp[i - 1] + nums[i];
        }
        max = Math.max(dp[i],max);
    }
    return max;
}

通過這種方式，不但計算出了當前序列的最大子序列和，并且還把以每一個元素結尾的最大連續(xù)子序列和也計算出來了。

通過這種方式的實現(xiàn)，空間復雜度為O(n)，時間復雜度為O(n)

優(yōu)化

由于現(xiàn)在的這種實現(xiàn)方式，空間復雜度比較高，通過對前面流程的分析，可以知道，在計算dp(i)的值時，只需要使用到dp(i - 1)的值，所以可以考慮將數(shù)組中的元素數(shù)量進行優(yōu)化，優(yōu)化后的結果如下

static int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int dp = nums[0];
    int max = dp;
    System.out.println("dp[0] = " + dp);
    for (int i = 1; i < nums.length; i++) {
        if (dp < 0) {
            dp = nums[i];
        } else {
            dp +=  nums[i];
        }
        max = Math.max(dp,max);
        System.out.println("dp[" + i + "] = " + dp);
    }
    return max;
}

通過這種方式進行優(yōu)化以后，空間復雜度變?yōu)榱薕(1)

場景三:最長上升子序列(LIS)[LeetCode]

最長上升子序列(最長遞增子序列，Longest Increasing Subsequence,LIS)

給定一個無序的整數(shù)序列，求出它最長上升子序列的長度（要求嚴格上升）

比如[10,2,2,5,1,7,101,18]的最長上升子序列是[2,5,7,101],[2,5,7,18],長度為4

定義狀態(tài)：

上面要求求出最長上升子序列的長度，也就意味著，需要知道最長上升子序列的結果是什么。其實結合場景二的問題可以發(fā)現(xiàn)，最長上升的子序列，依然可以利用計算以nums(i - 1)時元素的最長上升子序列，進而推導出nums(i)時元素的最長上升子序列，所以通過上面的序列，可以得到以下的計算過程

1. 以nums[0],即10結尾的最長上升子序列是10，即dp(0) = 1
2. 以nums[1],即2結尾的最長上升子序列是(2)，即dp(1) = 1
3. 以nums[2],即2結尾的最長上升子序列是(2)，即dp(2) = 1
4. 以nums[3],即5結尾的最長上升子序列是(2,5)，即dp(3) = 2
5. 以nums[4],即1結尾的最長上升子序列是(2,5)，即dp(4) = 2
6. 以nums[5],即7結尾的最長上升子序列是(2,5,7)，即dp(5) = 3
7. 以nums[6],即101結尾的最長上升子序列是(2,5,7,101)，即dp(6) = 4
8. 以nums[7],即18結尾的最長上升子序列是(2,5,7,18)，即dp(7) = 4

所以，最長上升子序列的長度是所有dp(i)中的最大值max{dp(i)},i∈[0,nums.length)

狀態(tài)轉移方程

設定另外一個變量j，其中j屬于[0,j)

遍歷j中的所有dp

• 當nums[i] > nums[j]時
  • 說明nums[i]可以接在nums[j]后面， 形成一個比dp[j]更長的上升子序列，長度為dp(j) + 1
  • dp(i) = max(dp(i),dp(j) + 1)
• 當nums[i] <= nums[j]時
  • nums[i]不能接在nums[j]后面，需要跳過此次遍歷

其中，初始狀態(tài)dp[0] = 1;

所以，結合前面的分析，可以得到如下的代碼

static int lengthOfLongestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    dp[0] = 1;
    int max = 1;
    for (int i = 1; i < dp.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] <= nums[j]) continue;
            dp[i] = Math.max(dp[i],dp[j] + 1);
        }
        max = Math.max(dp[i],max);
    }
    return max;
}

通過這種方式實現(xiàn)，其空間復雜度為O(n)，時間復雜度為O(n^2)。需要注意，這里的空間復雜度不能像前面場景二的方式進行優(yōu)化，因為每當要計算i為的dp值時，需要i前面所有的dp值，每一次都要用到前面的dp值，所以每一個dp值都需要存儲，因此不能優(yōu)化

不過，最長上升子序列還有更優(yōu)的解法。可以利用二分搜索的思路來解決。由于在本節(jié)中主要是對動態(tài)規(guī)劃進行討論，所以二分搜索這種思路，在后面再進行介紹。接下來，繼續(xù)對動態(tài)規(guī)劃這種策略進行深入探討。

場景四：最長公共子序列(LCS)[LeetCode]

最長公共子序列（Longest Common Subsequence,LCS）

即表達的意思為：求兩個序列的最長公共子序列長度，例如

• [1,3,5,9,10]和[1,4,9,10]的最長公共子序列是[1,9,10]，長度為3
• ABCBDAB和BDCABA的最長公共子序列長度是4
  • ABCBDAB和BDCABA >BDAB
  • ABCBDAB和BDCABA > BDAB
  • ABCBDAB和BDCABA > BCAB
  • ABCBDAB和BDCABA > BCBA

可以發(fā)現(xiàn)，這個問題與前面的最大連續(xù)子序列/最長上升子序列非常相似，所以依然可以利用動態(tài)規(guī)劃的方式來進行解決。

前面在利用動態(tài)規(guī)劃來解決問題時，首先要做的就是定義狀態(tài)。但是在該場景下，不同的地方在于，這里有2個序列，所以現(xiàn)在的狀態(tài)，就會與前面的不一樣了

思路

現(xiàn)假設2個序列分別是nums1，nums2；并定義如下兩個變量

• i ∈ [0,nums1.length]
• j ∈ [0,nums2.length]

然后，利用這兩個參數(shù)來定義狀態(tài)

假設dp(i,j)是【nums1前i個元素】與【nums2的前j個元素】的最長公共子序列，可以得到以下的信息

1. dp(i,0),dp(0,j)初始值均為0

2. 并且如果nums1[i-1] (即nums1中的第i位)位的元素與nums2[j - 1] (即nums2中的第i位)位的元素相等的話，則有d(i,j) = dp(i - 1, j - 1) +1(只比較最后一位的元素是否相等即可，然后利用小的子問題，推導出大的子問題)

3. 如果nums1[i-1] (即nums1中的第i位)位的元素與nums2[j - 1] (即nums2中的第i位)位的元素不相等的話，則存在兩種情況

   • 查看nums1的nums1[i - 2]與nums2[i - 1]的最長公共子序列是多少。因為可能nums2新增的這個元素，雖然不與nums1新增的這個元素相等， 但是可能與nums1[i - 2]序列中的元素相等
   • 查看nums2的nums2[i - 2]與nums1[i - 1]的最長公共子序列是多少。原因同上

   所以，如果nums1[i - 1] ≠ nums2[j - 1],那么dp(i,j) = max{dp(i - 1,j),dp(i,j - 1)}

   這樣，就確定了該問題的狀態(tài)轉移方程。

利用前面的分析，通過遞歸的方式實現(xiàn)如下：

static int longestCommonSubsequence(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    return longestCommonSubsequence(nums1,nums1.length,nums2,nums2.length);
}

/*
* 求nums1前i個元素與nums2前j個元素的最長公共子序列
* */
static int longestCommonSubsequence(int[] nums1,int i,int[] nums2, int j) {
    if (i == 0 || j == 0) return 0;
    if (nums1[i - 1] == nums2[j - 1]) {
        return longestCommonSubsequence(nums1,i - 1,nums2,j - 1) +1;
    }
    //最后一個元素不相等
    return Math.max(longestCommonSubsequence(nums1,i,nums2,j - 1),longestCommonSubsequence(nums1,i - 1,nums2,j ));
}

這種方式實現(xiàn)的空間復雜度為：O(k)，其中k = min{n,m},n,m是2個序列的長度；

由于這里的空間復雜度主要取決于遞歸的深度，所以，可以發(fā)現(xiàn)，當n,m中有一個值遞減為0時，遞歸就會結束，所以取決于兩個序列中長度更短的序列。

時間復雜度為：O(2^n)，當n = m 時

將上面的遞歸實現(xiàn)改為非遞歸實現(xiàn)，結果如下

static int longestCommonSubsequence(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    for (int i = 1; i <= nums1.length; i++) {
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1] );
            }
        }
    }
    return dp[nums1.length][nums2.length];
}

這種方式實現(xiàn)

• 空間復雜度為：O(n*m)
• 時間復雜度為：O(n*m)

通過觀察可以發(fā)現(xiàn)，dp(i,j)值的來源有三個地方，分別是dp[i - 1] [j - 1]，dp[i - 1] [j] ，dp[i] [j - 1]。所以前面定義的二維數(shù)組，當計算到后面(i增大以后)的值時，前面存儲的一些值，其實永遠也用不上了，使用到的值可能是第i行的數(shù)據與i - 1行的數(shù)據，所以可以通過這種方式，利用滾動數(shù)組對上面的實現(xiàn)進行優(yōu)化。

優(yōu)化后的結果如下：

static int longestCommonSubsequence(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[][] dp = new int[2][nums2.length + 1];
    for (int i = 1; i <= nums1.length; i++) {
        int row = i & 1;
        int prevRow = (i - 1) & 1;
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[row][j] = dp[prevRow][j - 1] + 1;
            } else {
                dp[row][j] = Math.max(dp[prevRow][j],dp[row][j - 1] );
            }
        }
    }
    return dp[nums1.length & 1][nums2.length];
}

將二維數(shù)組進一步優(yōu)化為一維數(shù)組

static int longestCommonSubsequence(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[] dp = new int[nums2.length + 1];
    for (int i = 1; i <= nums1.length; i++) {
        int cur = 0;//保存左上角的值
        for (int j = 1; j <= nums2.length; j++) {
            int leftTop = cur;
            cur = dp[j];
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[j] = leftTop + 1;
            } else {
                dp[j] = Math.max(dp[j],dp[j - 1] );
            }
        }
    }
    return dp[nums2.length];
}

由于發(fā)現(xiàn)，nums1和nums2，在循環(huán)操作是，哪個數(shù)組作為i變量，哪個數(shù)組作為j變量，其實是沒有影響的，通過兩個循環(huán)，都能考慮到所有的情況，所以基于這種情況，可以進一步將dp數(shù)組的空間進行優(yōu)化?？梢赃x擇length更小的數(shù)組來作為dp數(shù)組的長度

優(yōu)化后的結果如下

static int longestCommonSubsequence(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[] rowsNums = nums1, colsNums = nums2;
    if (nums1.length < nums2.length) {
        rowsNums = nums2;
        colsNums = nums1;
    }
    int[] dp = new int[colsNums.length + 1];
    for (int i = 1; i <= rowsNums.length; i++) {
        int cur = 0;//保存左上角的值
        for (int j = 1; j <= colsNums.length; j++) {
            int leftTop = cur;
            cur = dp[j];
            if (rowsNums[i - 1] == colsNums[j - 1]) {
                dp[j] = leftTop + 1;
            } else {
                dp[j] = Math.max(dp[j],dp[j - 1] );
            }
        }
    }
    return dp[colsNums.length];
}

通過這種優(yōu)化，不管從空間復雜度還是時間復雜度，都已經達到了最優(yōu)。

場景五：最長公共子串

最長公共子串（Longest Common Substring）

• 子串是連續(xù)的子序列

例如：ABCBA和BABCA的最長公共子串是ABC,長度為3

思路

假設兩個字符串分別為str1,str2，并定義如下兩個變量

• i ∈ [0,str1.length]
• j ∈ [0,str2.length]

假設狀態(tài)dp(i,j)是以str1[i - 1],str2[j - 1]結尾的最長公共子串長度
其中規(guī)定dp(i,0),dp(0,j)的初始值均為0

所以，結合前面最長公共子序列的經驗可以知道有如下轉移方程情況

• str1[i - 1] = str2[j - 1],那么dp(i,j) = dp(i - 1,j - 1) + 1
• str1[i - 1] ≠ str2[j - 1],那么dp(i,j) = 0

最終，期望得到的值就是所有dp(i,j)中最大的值，即max{dp(i,j)}

通過上面的思路，最終得到的代碼如下

static int longestCommonSubstring(String str1,String str2) {
    if (str1 == null || str2 == null) return 0;
    if (str1.length() == 0 || str2.length() == 0) return 0;
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    char[] chars1 = str1.toCharArray();
    char[] chars2 = str2.toCharArray();
    int max = 0;
    for (int i = 1; i <= chars1.length; i++) {
        for (int j = 1; j <= chars2.length; j++) {
            if (chars1[i - 1] == chars2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(max,dp[i][j]);
            }
//                else {//值默認就是0 所以不用賦值
//                    dp[i][j] = 0;
//                }
        }
    }
    return max;
}

通過這種實現(xiàn)的空間復雜度與時間復雜度為：O(n*m)。結合前面最長公共子序列的優(yōu)化經驗可以知道，這里的二維數(shù)組同樣可以進行優(yōu)化，因為計算dp[i] [j]的值時，只會用到dp[i - 1] [j - 1]的值，所以優(yōu)化思路和最長公共子串是一樣的。

所以，優(yōu)化后的結果如下：

static int longestCommonSubstring(String str1,String str2) {
    if (str1 == null || str2 == null) return 0;
    if (str1.length() == 0 || str2.length() == 0) return 0;
    char[] chars1 = str1.toCharArray();
    char[] chars2 = str2.toCharArray();
    char[] rowsChars = chars1,colsChars = chars2;
    if (chars1.length < chars2.length) {
        rowsChars = chars2;
        colsChars = chars1;
    }
    int[] dp = new int[colsChars.length + 1];
    int max = 0;
    for (int row = 1; row <= rowsChars.length; row++) {
        int cur = 0;
        for (int col = 1; col <= colsChars.length; col++) {
            int leftTop = cur;
            cur = dp[col];
            if (chars1[row - 1] == chars2[col - 1]) {
                dp[col] = leftTop + 1;
                max = Math.max(max,dp[col]);
            }
            else {
                dp[col] = 0;
            }
        }
    }
    return max;
}

通過優(yōu)化后，空間復雜度為：O(k)，k = min(m,n);

時間復雜度為：O(n*m)

場景六：0-1背包問題

0-1背包問題，在討論貪心策略時，曾經介紹過該問題，但是當時也說到，利用貪心策略來解決該問題時，并不靠譜，因為根據不同的優(yōu)先策略最終得到結果并不一樣，所以并不靠譜，但是，如果利用動態(tài)規(guī)劃的策略來解決該問題的話，最終的結果，就很固定了。

首先來回顧一下0-1背包問題的場景

有n件物品和一個最大承重為W的背包，沒見物品的重量是w，價值是v

在保證總重量不超過W的前提下，將哪幾件物品裝入背包，可使得背包的總價值最大？

所以，現(xiàn)在就考慮使用動態(tài)規(guī)劃來解決該問題。

定義狀態(tài)：

現(xiàn)假設values是價值數(shù)組，weights是重量數(shù)組

• 編號為k的物品，價值是values[k]，重量為weights[k]，其中k∈[0,n)(n為物品的數(shù)量)

定義如下狀態(tài)
dp(i,j)表示最大承重為j時，有前i件物品可選時的最大總價值，其中i ∈ [0,n],j ∈ [0,W]

例如：dp(3,7)

現(xiàn)有10件物品，但是只能選擇前面的3件物品

最大承重量為7

初始值：

dp(i,0),dp(0,j)初始值為0；因為分別表示最大承重量為0時和可選的物品為0時的狀態(tài)

那么，dp{i,j}如何才能通過子問題推導出來呢？

當面臨i件物品時，有兩種選擇，

• 如果不選擇第i件物品時，dp(i,j) = dp(i - 1, j)，因為在第i件物品時，沒有選，所以背包的稱重量沒有發(fā)生變換，只是現(xiàn)在的情況下，可選的物品比原來多了一件，但是最終的價值是一樣的
• 如果選擇第i件物品時，dp(i,j) = dp(i - 1, j - weights[i - 1]) + values[i - 1]

最終決定是否選擇該件物品由最終的價值決定，所以取這兩種情況中的最大值dp(i,j) = max(dp(i - 1, j),dp(i - 1, j - weights[i - 1]) + valuess[i - 1])

不過需要注意，除了上面容易考慮到的兩種情況以外，還有另外一種情況，即當前最大稱重量j小于第i件物品的重量時，該件物品就不可能選擇，所以這個時候，有i件物品可選與i-1件物品可選時的結果是一樣的，所以這個時候的結果為dp(i,j) = dp(i - 1, j)

所以，最終的狀態(tài)轉移方程如下

• j < weights[i - 1]，那么dp(i,j) = dp(i - 1, j)
• j ≥ weights[i - 1]，那么dp(i,j) = max(dp(i - 1, j),dp(i - 1, j - weights[i - 1]) + valuess[i - 1])

通過上面的分析思路，最終得到的代碼如下

static int maxValue(int[] values,int[] weights, int capacity) {
    if (
            values == null || 
            weights == null || 
            values.length == 0 || 
            weights.length == 0 || 
            values.length != weights.length || 
            capacity <= 0
    ) return 0;
    int[][] dp = new int[values.length + 1][capacity + 1];
    for (int i = 1; i <= values.length; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j < weights[i - 1]) {//當前最大稱重量j小于第i件物品的重量時
                dp[i][j] = dp[i - 1][j];
            } else  {
                dp[i][j] = Math.max(dp[i - 1][j],values[i - 1] + dp[i - 1][j - weights[i - 1]]);
            }
        }
    }
    return dp[values.length][capacity];
}

結合前面的經驗，可以知道，計算第i行數(shù)據時，只會用到i-1行的數(shù)據，所以可以想到，dp數(shù)組是可以進行優(yōu)化的。而且在利用前面的值計算后面的值時，用到了dp[i - 1] [j - weights[i - 1]]的值進行計算，所以如果還是用前面的方法來進行優(yōu)化的話，[j - weights[i - 1]]的值是拿不到的，因為會被覆蓋，所以為了保證能拿到[j - weights[i - 1]]的數(shù)據，現(xiàn)在考慮利用重量大的情況，推導出重量小的情況。這樣就不會覆蓋[j - weights[i - 1]]的值

最終，優(yōu)化后的結果如下

static int maxValue(int[] values,int[] weights, int capacity) {
    if (
            values == null ||
                    weights == null ||
                    values.length == 0 ||
                    weights.length == 0 ||
                    values.length != weights.length ||
                    capacity <= 0
    ) return 0;
    int[] dp = new int[capacity + 1];
    for (int i = 1; i <= values.length; i++) {
        for (int j = capacity; j >= 1; j--) {
            if (j < weights[i - 1]) continue;
               dp[j] = Math.max(dp[j],values[i - 1] + dp[j - weights[i - 1]]);
        }
    }
    return dp[capacity];
}

擴展

最長上升子序列-二分搜索實現(xiàn)

在前面，利用動態(tài)規(guī)劃遍歷序列來進行查找，所以，通過動態(tài)規(guī)劃的方式來查找，其時間復雜度為O(n^2)，如果使用二分搜索的方式實現(xiàn)，則會更優(yōu)。其思路如下

假設序列如下圖所示

為了能更好的理解，現(xiàn)在請將每一個數(shù)組都看做為一張撲克牌，然后從左往右按順序處理每一張撲克牌

• 將正在處理的牌，放在第一張大于等于當前牌的牌堆之上
• 如果找不到第一張牌大于等于當前正在處理的牌的牌堆時，就將它放入一個新的牌堆中

例如，

1. 在最開始的時候，拿到的是10這張牌，但是這時候沒有牌堆，所以這個時候10會成立一個新的牌堆

2. 接下來，會拿到2這張牌，通過從左往右尋找牌堆，所以先找到了10這個牌堆，這個牌堆的牌頂是10，10這張牌是大于2這張牌的，所以會將2這張牌壓在10這張牌的上面，結果如下

3. 接下來，繼續(xù)出列下一張牌2，通過尋找牌堆，發(fā)現(xiàn)現(xiàn)在有一個牌堆的牌頂是2，所以就會將正在處理的這張牌，壓到牌頂為2的牌堆上，結果如下

4. 接下來，會拿到5這張牌，然后從左往右查找，并沒有發(fā)現(xiàn)牌頂大于等于5的牌堆，所以會新建一個牌堆

5. 然后拿到下一章牌1，并且從左往右開始尋找牌堆，發(fā)現(xiàn)當前有一個牌堆的牌頂為2，大于等于當前的牌，所以就會將1這張牌，放在牌頂為2的牌堆中

6. 拿到下一章牌7，發(fā)現(xiàn)所有牌堆的牌頂都不大于當前的牌，所以會新建一個牌堆，最終的結果如下

7. 繼續(xù)拿到下一張牌101，依然發(fā)現(xiàn)所有牌堆的牌頂都不大于當前的牌，所以又會新建一個牌堆，結果如下

8. 接下來，會拿到最后一張牌18，從左往右查找發(fā)現(xiàn)，前面3個牌堆的牌頂都不大于當前的牌，所以最終18會放到最后一個牌堆上

現(xiàn)在，所有牌都已經排好了，并且發(fā)現(xiàn)，現(xiàn)在的最長上升子序列已經產生了，為2,5,7,101或者2,5,7,18.并且最終牌堆的數(shù)量，就是最長上升子序列的長度，且組成的元素來自于4個牌堆，通過這種思路，得到的代碼如下

static int lengthOfLongestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int len = 0;//牌堆的數(shù)量
    int[] top = new int[nums.length];//牌頂數(shù)組
    //遍歷所有的牌
    for (int num : nums) {
        int i = 0;
        for (; i < len; i++) {
            if (top[i] >= num) {//找到了一個大于等于num的牌頂
                top[i] = num;
                break;
            }
        }
        if (i == len) {
            //所有牌頂小于當前的牌,新建牌堆
            len++;
            top[i] = num;
        }
    }
    return len;
}

通過這種方式實現(xiàn)，可以發(fā)現(xiàn)如果是最壞的情況的話，時間復雜度依然是O(n^2)，所以對比動態(tài)規(guī)劃，也沒有太多的提升。所以在這種情況下，可以利用二分搜索來進行優(yōu)化。

由于發(fā)現(xiàn)牌堆從左往右的牌頂，是升序的。當有一個新的牌要放在合適的位置時，就可以利用二分搜索的方式來找到其對應的位置，然后找到位置后，直接覆蓋牌頂即可，所以通過二分搜索優(yōu)化后的結果如下

static int lengthOfLongestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int len = 0;//牌堆的數(shù)量
    int[] top = new int[nums.length];//牌頂數(shù)組
    //遍歷所有的牌
    for (int num : nums) {
        int begin = 0;
        int end = len;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (num <= top[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        //覆蓋牌頂
        top[begin] = num;
        //檢查是否要新建牌堆
        if (begin == len) len++;
    }
    return len;
}

demo下載地址

完！