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

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

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

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

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

場景一：找零錢[LeetCode]

假設有25分瓢对，20分，5分胰苏，1分的硬幣硕蛹，現在要找給客戶41分零錢，如何辦到硬幣個數最少

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

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

• 如果第一次選擇了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;

所以現在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中情況中選出硬幣數量最少的一種葡缰，就是dp(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ā)現，上面這種計算硬幣最少數量的解法韭畸，與前面介紹的斐波那鍥數列的解法非常相似宇智，存在非常多的重復計算問題，所以可以使用記憶搜索來進行優(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)化方式依然是采用自頂向下的方式來計算的甘萧，并且依然是遞歸調用萝嘁， 所以還存在棧空間的開銷扬卷，所以現在可以考慮采用另外的方式進行優(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)

現在蚕断，通過遞推的方式，將上面求解的代碼進行整合入挣，變得更加通用亿乳，結果如下

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ī)劃径筏？

現在來回顧一下解決該問題风皿，經過的步驟。

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

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

后來，發(fā)現在進行暴力遞歸時指黎，有很多重復的計算朋凉，所以就將暴力遞歸的方式進行了優(yōu)化，改為了記憶化搜索的方式醋安，記錄某一面值杂彭，需要硬幣數量的情況。但是記憶化搜索僅僅是解決了重復計算的問題吓揪， 它依然是自上而下的一種調用方式亲怠，并沒有解決遞歸調用实蓬，消耗椙⒔啵空間的問題。

最終晦譬，經過進一步的觀察叭首，發(fā)現可以將自頂向下的方式改為自底向上地方方式來進行計算习勤，通過計算出較小的值，然后利用較小的值推導出較大值的這種方式焙格，這樣的話图毕，就將遞歸調用給去掉了，所以最終的實現间螟，就變?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分需要的硬幣個數见坑，所以dp(41)就表示湊夠41分嚷掠，需要的硬幣個數；dp(4)就問湊夠4分荞驴，需要的硬幣個數

     可以發(fā)現不皆，定義的狀態(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)犬耻，比如現一直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)的值是多少绘梦，并不關心這些值是怎么計算出來的

無后效性舉例

現在有如下圖所示的5*5格子

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

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

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

可以發(fā)現，定義的這個狀態(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)一共的走法月褥。

在這里，無后效性體現在:

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

有后效性舉例

現在同樣有如下的格子

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

有后效性體現在

現在假設要走到(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的整數序列，求它的最大連續(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)

實現代碼如下

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ù)子序列和也計算出來了膨俐。

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

優(yōu)化

由于現在的這種實現方式焚刺，空間復雜度比較高，通過對前面流程的分析门烂，可以知道乳愉，在計算dp(i)的值時，只需要使用到dp(i - 1)的值屯远，所以可以考慮將數組中的元素數量進行優(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)

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

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

定義狀態(tài)：

上面要求求出最長上升子序列的長度，也就意味著房揭，需要知道最長上升子序列的結果是什么备闲。其實結合場景二的問題可以發(fā)現，最長上升的子序列捅暴，依然可以利用計算以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;
}

通過這種方式實現，其空間復雜度為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ā)現浴捆，這個問題與前面的最大連續(xù)子序列/最長上升子序列非常相似，所以依然可以利用動態(tài)規(guī)劃的方式來進行解決稿械。

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

思路

現假設2個序列分別是nums1窝撵，nums2；并定義如下兩個變量

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

然后襟铭，利用這兩個參數來定義狀態(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)轉移方程。

利用前面的分析碉考，通過遞歸的方式實現如下：

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 ));
}

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

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

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

將上面的遞歸實現改為非遞歸實現伊脓，結果如下

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];
}

這種方式實現

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

通過觀察可以發(fā)現，dp(i,j)值的來源有三個地方魁衙，分別是dp[i - 1] [j - 1]报腔，dp[i - 1] [j] ，dp[i] [j - 1]剖淀。所以前面定義的二維數組纯蛾，當計算到后面(i增大以后)的值時，前面存儲的一些值纵隔，其實永遠也用不上了翻诉，使用到的值可能是第i行的數據與i - 1行的數據，所以可以通過這種方式捌刮，利用滾動數組對上面的實現進行優(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];
}

將二維數組進一步優(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[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ā)現，nums1和nums2绅作，在循環(huán)操作是芦圾，哪個數組作為i變量，哪個數組作為j變量俄认，其實是沒有影響的堕扶，通過兩個循環(huán)，都能考慮到所有的情況梭依，所以基于這種情況稍算，可以進一步將dp數組的空間進行優(yōu)化∫鬯可以選擇length更小的數組來作為dp數組的長度

優(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;
}

通過這種實現的空間復雜度與時間復雜度為：O(n*m)。結合前面最長公共子序列的優(yōu)化經驗可以知道弃酌，這里的二維數組同樣可以進行優(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的前提下，將哪幾件物品裝入背包凌蔬，可使得背包的總價值最大露懒？

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

定義狀態(tài)：

現假設values是價值數組懈词，weights是重量數組

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

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

例如：dp(3,7)

現有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ā)生變換谭网，只是現在的情況下，可選的物品比原來多了一件赃春，但是最終的價值是一樣的
• 如果選擇第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行數據時峭梳，只會用到i-1行的數據，所以可以想到蹂喻，dp數組是可以進行優(yōu)化的葱椭。而且在利用前面的值計算后面的值時，用到了dp[i - 1] [j - weights[i - 1]]的值進行計算口四，所以如果還是用前面的方法來進行優(yōu)化的話孵运，[j - weights[i - 1]]的值是拿不到的，因為會被覆蓋蔓彩，所以為了保證能拿到[j - weights[i - 1]]的數據掐松，現在考慮利用重量大的情況踱侣，推導出重量小的情況。這樣就不會覆蓋[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];
}

擴展

最長上升子序列-二分搜索實現

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

假設序列如下圖所示

為了能更好的理解，現在請將每一個數組都看做為一張撲克牌绳瘟，然后從左往右按順序處理每一張撲克牌

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

例如糖声，

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

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

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

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

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

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

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

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

現在藐窄，所有牌都已經排好了资昧，并且發(fā)現，現在的最長上升子序列已經產生了荆忍，為2,5,7,101或者2,5,7,18.并且最終牌堆的數量格带，就是最長上升子序列的長度，且組成的元素來自于4個牌堆东揣，通過這種思路践惑，得到的代碼如下

static int lengthOfLongestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int len = 0;//牌堆的數量
    int[] top = new int[nums.length];//牌頂數組
    //遍歷所有的牌
    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;
}

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

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

static int lengthOfLongestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int len = 0;//牌堆的數量
    int[] top = new int[nums.length];//牌頂數組
    //遍歷所有的牌
    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下載地址

完蒙袍！