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

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

-----------

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

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

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

先看一下題目媚送，很容易理解：

title

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

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

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

相信大家對數(shù)學歸納法都不陌生咱扣，高中就學過，而且思路很簡單涵防。比如我們想證明一個數(shù)學結(jié)論闹伪，那么我們先假設這個結(jié)論在 k<n 時成立，然后根據(jù)這個假設壮池，想辦法推導證明出 k=n 的時候此結(jié)論也成立偏瓤。如果能夠證明出來，那么就說明這個結(jié)論對于 k 等于任何數(shù)都成立椰憋。

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

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

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

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

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

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

舉兩個例子：

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

gif1

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

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

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

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

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

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

nums[5] = 3胸嘁，既然是遞增子序列，我們只要找到前面那些結(jié)尾比 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);
    }
}

結(jié)合我們剛才說的 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)呀伙。總結(jié)一下如何找到動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移關系：

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

        /***** 搜索左側(cè)邊界的二分查找 *****/
        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)的推演轉(zhuǎn)移是晨，最終得到答案。

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

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