動態(tài)規(guī)劃設計：最長遞增子序列

讀完本文澡刹，你可以去力扣拿下如下題目：

-----------

也許有讀者看了前文動態(tài)規(guī)劃詳解，學會了動態(tài)規(guī)劃的套路：找到了問題的「狀態(tài)」，明確了 dp 數(shù)組/函數(shù)的含義，定義了 base case；但是不知道如何確定「選擇」，也就是不到狀態(tài)轉移的關系，依然寫不出動態(tài)規(guī)劃解法茂浮，怎么辦？

不要擔心壳咕，動態(tài)規(guī)劃的難點本來就在于尋找正確的狀態(tài)轉移方程席揽，本文就借助經(jīng)典的「最長遞增子序列問題」來講一講設計動態(tài)規(guī)劃的通用技巧：數(shù)學歸納思想。

最長遞增子序列（Longest Increasing Subsequence谓厘，簡寫 LIS）是非常經(jīng)典的一個算法問題驹尼，比較容易想到的是動態(tài)規(guī)劃解法，時間復雜度 O(N^2)庞呕，我們借這個問題來由淺入深講解如何找狀態(tài)轉移方程新翎，如何寫出動態(tài)規(guī)劃解法。比較難想到的是利用二分查找住练，時間復雜度是 O(NlogN)地啰，我們通過一種簡單的紙牌游戲來輔助理解這種巧妙的解法。

先看一下題目讲逛，很容易理解：

title

注意「子序列」和「子串」這兩個名詞的區(qū)別亏吝，子串一定是連續(xù)的，而子序列不一定是連續(xù)的盏混。下面先來設計動態(tài)規(guī)劃算法解決這個問題蔚鸥。

一惜论、動態(tài)規(guī)劃解法

動態(tài)規(guī)劃的核心設計思想是數(shù)學歸納法。

相信大家對數(shù)學歸納法都不陌生止喷，高中就學過馆类，而且思路很簡單。比如我們想證明一個數(shù)學結論弹谁，那么我們先假設這個結論在 k<n 時成立乾巧，然后根據(jù)這個假設，想辦法推導證明出 k=n 的時候此結論也成立预愤。如果能夠證明出來沟于，那么就說明這個結論對于 k 等于任何數(shù)都成立。

類似的植康，我們設計動態(tài)規(guī)劃算法旷太，不是需要一個 dp 數(shù)組嗎？我們可以假設 dp[0...i-1] 都已經(jīng)被算出來了销睁，然后問自己：怎么通過這些結果算出 dp[i]供璧？

直接拿最長遞增子序列這個問題舉例你就明白了。不過榄攀，首先要定義清楚 dp 數(shù)組的含義嗜傅，即 dp[i] 的值到底代表著什么金句？

我們的定義是這樣的：dp[i] 表示以 nums[i] 這個數(shù)結尾的最長遞增子序列的長度檩赢。

PS：為什么這樣定義呢？這是解決子序列問題的一個套路违寞，后文動態(tài)規(guī)劃之子序列問題解題模板總結了幾種常見套路贞瞒。你讀完本章所有的動態(tài)規(guī)劃問題，就會發(fā)現(xiàn) dp 數(shù)組的定義方法也就那幾種趁曼。

根據(jù)這個定義军浆，我們就可以推出 base case：dp[i] 初始值為 1，因為以 nums[i] 結尾的最長遞增子序列起碼要包含它自己挡闰。

PS：我認真寫了 100 多篇原創(chuàng)乒融，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄摄悯，持續(xù)更新赞季。建議收藏，按照我的文章順序刷題奢驯，掌握各種算法套路后投再入題海就如魚得水了申钩。

舉兩個例子：

算法演進的過程是這樣的，：

gif1

根據(jù)這個定義瘪阁，我們的最終結果（子序列的最大長度）應該是 dp 數(shù)組中的最大值撒遣。

int res = 0;
for (int i = 0; i < dp.size(); i++) {
    res = Math.max(res, dp[i]);
}
return res;

讀者也許會問邮偎，剛才的算法演進過程中每個 dp[i] 的結果是我們?nèi)庋劭闯鰜淼模覀儜撛趺丛O計算法邏輯來正確計算每個 dp[i] 呢义黎？

這就是動態(tài)規(guī)劃的重頭戲了禾进，要思考如何設計算法邏輯進行狀態(tài)轉移，才能正確運行呢轩缤？這里就可以使用數(shù)學歸納的思想：

假設我們已經(jīng)知道了 dp[0..4] 的所有結果命迈，我們?nèi)绾瓮ㄟ^這些已知結果推出 dp[5] 呢？

根據(jù)剛才我們對 dp 數(shù)組的定義火的，現(xiàn)在想求 dp[5] 的值壶愤，也就是想求以 nums[5] 為結尾的最長遞增子序列。

nums[5] = 3馏鹤，既然是遞增子序列征椒，我們只要找到前面那些結尾比 3 小的子序列，然后把 3 接到最后湃累，就可以形成一個新的遞增子序列勃救，而且這個新的子序列長度加一。

顯然治力，可能形成很多種新的子序列蒙秒，但是我們只選擇最長的那一個，把最長子序列的長度作為 dp[5] 的值即可宵统。

gif2

for (int j = 0; j < i; j++) {
    if (nums[i] > nums[j]) 
        dp[i] = Math.max(dp[i], dp[j] + 1);
}

當 i = 5 時晕讲，這段代碼的邏輯就可以算出 dp[5]。其實到這里马澈，這道算法題我們就基本做完了瓢省。

讀者也許會問，我們剛才只是算了 dp[5] 呀痊班，dp[4], dp[3] 這些怎么算呢勤婚？類似數(shù)學歸納法，你已經(jīng)可以算出 dp[5] 了涤伐，其他的就都可以算出來：

for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) 
            dp[i] = Math.max(dp[i], dp[j] + 1);
    }
}

結合我們剛才說的 base case馒胆，下面我們看一下完整代碼：

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    // base case：dp 數(shù)組全都初始化為 1
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) 
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    
    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

至此，這道題就解決了凝果，時間復雜度 O(N^2)祝迂。總結一下如何找到動態(tài)規(guī)劃的狀態(tài)轉移關系：

1豆村、明確 dp 數(shù)組所存數(shù)據(jù)的含義液兽。這一步對于任何動態(tài)規(guī)劃問題都很重要，如果不得當或者不夠清晰，會阻礙之后的步驟四啰。

2宁玫、根據(jù) dp 數(shù)組的定義，運用數(shù)學歸納法的思想柑晒，假設 dp[0...i-1] 都已知欧瘪，想辦法求出 dp[i]，一旦這一步完成匙赞，整個題目基本就解決了佛掖。

但如果無法完成這一步，很可能就是 dp 數(shù)組的定義不夠恰當涌庭，需要重新定義 dp 數(shù)組的含義芥被；或者可能是 dp 數(shù)組存儲的信息還不夠，不足以推出下一步的答案坐榆，需要把 dp 數(shù)組擴大成二維數(shù)組甚至三維數(shù)組拴魄。

PS：我認真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目席镀，全部發(fā)布在 labuladong的算法小抄匹中，持續(xù)更新。建議收藏豪诲，按照我的文章順序刷題顶捷，掌握各種算法套路后投再入題海就如魚得水了。

二屎篱、二分查找解法

這個解法的時間復雜度為 O(NlogN)服赎，但是說實話，正常人基本想不到這種解法（也許玩過某些紙牌游戲的人可以想出來）芳室。所以大家了解一下就好专肪，正常情況下能夠給出動態(tài)規(guī)劃解法就已經(jīng)很不錯了刹勃。

根據(jù)題目的意思堪侯，我都很難想象這個問題竟然能和二分查找扯上關系。其實最長遞增子序列和一種叫做 patience game 的紙牌游戲有關荔仁，甚至有一種排序方法就叫做 patience sorting（耐心排序）伍宦。

為了簡單起見，后文跳過所有數(shù)學證明乏梁，通過一個簡化的例子來理解一下算法思路次洼。

首先，給你一排撲克牌遇骑，我們像遍歷數(shù)組那樣從左到右一張一張?zhí)幚磉@些撲克牌卖毁，最終要把這些牌分成若干堆。

poker1

處理這些撲克牌要遵循以下規(guī)則：

只能把點數(shù)小的牌壓到點數(shù)比它大的牌上；如果當前牌點數(shù)較大沒有可以放置的堆亥啦，則新建一個堆炭剪，把這張牌放進去；如果當前牌有多個堆可供選擇翔脱，則選擇最左邊的那一堆放置奴拦。

比如說上述的撲克牌最終會被分成這樣 5 堆（我們認為紙牌 A 的牌面是最大的，紙牌 2 的牌面是最小的）届吁。

poker2

為什么遇到多個可選擇堆的時候要放到最左邊的堆上呢错妖？因為這樣可以保證牌堆頂?shù)呐朴行颍?, 4, 7, 8, Q），證明略疚沐。

poker3

按照上述規(guī)則執(zhí)行暂氯，可以算出最長遞增子序列，牌的堆數(shù)就是最長遞增子序列的長度亮蛔，證明略株旷。

LIS

我們只要把處理撲克牌的過程編程寫出來即可。每次處理一張撲克牌不是要找一個合適的牌堆頂來放嗎尔邓，牌堆頂?shù)呐撇皇?strong>有序嗎晾剖，這就能用到二分查找了：用二分查找來搜索當前牌應放置的位置。

PS：舊文二分查找算法詳解詳細介紹了二分查找的細節(jié)及變體梯嗽，這里就完美應用上了齿尽，如果沒讀過強烈建議閱讀。

public int lengthOfLIS(int[] nums) {
    int[] top = new int[nums.length];
    // 牌堆數(shù)初始化為 0
    int piles = 0;
    for (int i = 0; i < nums.length; i++) {
        // 要處理的撲克牌
        int poker = nums[i];

        /***** 搜索左側邊界的二分查找 *****/
        int left = 0, right = piles;
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        /*********************************/
        
        // 沒找到合適的牌堆灯节，新建一堆
        if (left == piles) piles++;
        // 把這張牌放到牌堆頂
        top[left] = poker;
    }
    // 牌堆數(shù)就是 LIS 長度
    return piles;
}

至此循头，二分查找的解法也講解完畢。

這個解法確實很難想到炎疆。首先涉及數(shù)學證明卡骂，誰能想到按照這些規(guī)則執(zhí)行，就能得到最長遞增子序列呢形入？其次還有二分查找的運用全跨，要是對二分查找的細節(jié)不清楚，給了思路也很難寫對亿遂。

所以浓若，這個方法作為思維拓展好了。但動態(tài)規(guī)劃的設計方法應該完全理解：假設之前的答案已知蛇数，利用數(shù)學歸納的思想正確進行狀態(tài)的推演轉移挪钓，最終得到答案。

＿＿＿＿＿＿＿＿＿＿＿＿＿

我的在線電子書有 100 篇原創(chuàng)文章耳舅，手把手帶刷 200 道力扣題目碌上，建議收藏！對應的 GitHub 算法倉庫已經(jīng)獲得了 70k star，歡迎標星馏予！