注：此文只在個(gè)人總結(jié) labuladong 動(dòng)態(tài)規(guī)劃框架，僅限于學(xué)習(xí)交流，版權(quán)歸原作者所有；

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

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

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

力扣第 300 題「最長(zhǎng)遞增子序列open in new window」就是這個(gè)問(wèn)題：

輸入一個(gè)無(wú)序的整數(shù)數(shù)組，請(qǐng)你找到其中最長(zhǎng)的嚴(yán)格遞增子序列的長(zhǎng)度，函數(shù)簽名如下：

int lengthOfLIS(int[] nums);

比如說(shuō)輸入 nums=[10,9,2,5,3,7,101,18]，其中最長(zhǎng)的遞增子序列是 [2,3,7,101]，所以算法的輸出應(yīng)該是 4。

注意「子序列」和「子串」這兩個(gè)名詞的區(qū)別，子串一定是連續(xù)的，而子序列不一定是連續(xù)的。下面先來(lái)設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法解決這個(gè)問(wèn)題。

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

動(dòng)態(tài)規(guī)劃的核心設(shè)計(jì)思想是數(shù)學(xué)歸納法。

相信大家對(duì)數(shù)學(xué)歸納法都不陌生，高中就學(xué)過(guò)，而且思路很簡(jiǎn)單。比如我們想證明一個(gè)數(shù)學(xué)結(jié)論，那么我們先假設(shè)這個(gè)結(jié)論在 k < n 時(shí)成立，然后根據(jù)這個(gè)假設(shè)，想辦法推導(dǎo)證明出 k = n 的時(shí)候此結(jié)論也成立。如果能夠證明出來(lái)，那么就說(shuō)明這個(gè)結(jié)論對(duì)于 k 等于任何數(shù)都成立。

類(lèi)似的，我們?cè)O(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，不是需要一個(gè) dp 數(shù)組嗎？我們可以假設(shè) dp[0...i-1] 都已經(jīng)被算出來(lái)了，然后問(wèn)自己：怎么通過(guò)這些結(jié)果算出 dp[i]？

直接拿最長(zhǎng)遞增子序列這個(gè)問(wèn)題舉例你就明白了。不過(guò)，首先要定義清楚 dp 數(shù)組的含義，即 dp[i] 的值到底代表著什么？

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

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

根據(jù)這個(gè)定義，我們就可以推出 base case：dp[i] 初始值為 1，因?yàn)橐?nums[i] 結(jié)尾的最長(zhǎng)遞增子序列起碼要包含它自己。

舉兩個(gè)例子：

這個(gè) GIF 展示了算法演進(jìn)的過(guò)程：

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

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

讀者也許會(huì)問(wèn)，剛才的算法演進(jìn)過(guò)程中每個(gè) dp[i] 的結(jié)果是我們?nèi)庋劭闯鰜?lái)的，我們應(yīng)該怎么設(shè)計(jì)算法邏輯來(lái)正確計(jì)算每個(gè) dp[i] 呢？

這就是動(dòng)態(tài)規(guī)劃的重頭戲，如何設(shè)計(jì)算法邏輯進(jìn)行狀態(tài)轉(zhuǎn)移，才能正確運(yùn)行呢？這里需要使用數(shù)學(xué)歸納的思想：

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

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

nums[5] = 3，既然是遞增子序列，我們只要找到前面那些結(jié)尾比 3 小的子序列，然后把 3 接到這些子序列末尾，就可以形成一個(gè)新的遞增子序列，而且這個(gè)新的子序列長(zhǎng)度加一。

nums[5] 前面有哪些元素小于 nums[5]？這個(gè)好算，用 for 循環(huán)比較一波就能把這些元素找出來(lái)。

以這些元素為結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度是多少？回顧一下我們對(duì) dp 數(shù)組的定義，它記錄的正是以每個(gè)元素為末尾的最長(zhǎng)遞增子序列的長(zhǎng)度。

以我們舉的例子來(lái)說(shuō)，nums[0] 和 nums[4] 都是小于 nums[5] 的，然后對(duì)比 dp[0] 和 dp[4] 的值，我們讓 nums[5] 和更長(zhǎng)的遞增子序列結(jié)合，得出 dp[5] = 3：

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

當(dāng) i = 5 時(shí)，這段代碼的邏輯就可以算出 dp[5]。其實(shí)到這里，這道算法題我們就基本做完了。

讀者也許會(huì)問(wèn)，我們剛才只是算了 dp[5] 呀，dp[4], dp[3] 這些怎么算呢？類(lèi)似數(shù)學(xué)歸納法，你已經(jīng)可以算出 dp[5] 了，其他的就都可以算出來(lái)：

for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < i; j++) {
        // 尋找 nums[0..j-1] 中比 nums[i] 小的元素
        if (nums[i] > nums[j]) {
            // 把 nums[i] 接在后面，即可形成長(zhǎng)度為 dp[j] + 1，
            // 且以 nums[i] 為結(jié)尾的遞增子序列
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

結(jié)合我們剛才說(shuō)的 base case，下面我們看一下完整代碼：

int lengthOfLIS(int[] nums) {
    // 定義：dp[i] 表示以 nums[i] 這個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
    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;
}

至此，這道題就解決了，時(shí)間復(fù)雜度 O(N^2)?？偨Y(jié)一下如何找到動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移關(guān)系：

1、明確 dp 數(shù)組的定義。這一步對(duì)于任何動(dòng)態(tài)規(guī)劃問(wèn)題都很重要，如果不得當(dāng)或者不夠清晰，會(huì)阻礙之后的步驟。

2、根據(jù) dp 數(shù)組的定義，運(yùn)用數(shù)學(xué)歸納法的思想，假設(shè) dp[0...i-1] 都已知，想辦法求出 dp[i]，一旦這一步完成，整個(gè)題目基本就解決了。

但如果無(wú)法完成這一步，很可能就是 dp 數(shù)組的定義不夠恰當(dāng)，需要重新定義 dp 數(shù)組的含義；或者可能是 dp 數(shù)組存儲(chǔ)的信息還不夠，不足以推出下一步的答案，需要把 dp 數(shù)組擴(kuò)大成二維數(shù)組甚至三維數(shù)組。

目前的解法是標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃，但對(duì)最長(zhǎng)遞增子序列問(wèn)題來(lái)說(shuō)，這個(gè)解法不是最優(yōu)的，可能無(wú)法通過(guò)所有測(cè)試用例了，下面講講更高效的解法。

注：核心問(wèn)題是 2 個(gè)：

1. dp 數(shù)組的定義：最好能直接對(duì)應(yīng)問(wèn)題，如最長(zhǎng)遞增子序列中 dp 數(shù)組表示以 nums[i] 結(jié)尾的最長(zhǎng)的遞增最序列；
2. dp 數(shù)組的推理：即知道 dp[0...i-1] 都已知，如何求出 dp[i]；

其中 dp 數(shù)組如何定義很重要！

二、拓展到二維

我們看一個(gè)經(jīng)常出現(xiàn)在生活中的有趣問(wèn)題，力扣第 354 題「俄羅斯套娃信封問(wèn)題open in new window」，先看下題目：

這道題目其實(shí)是最長(zhǎng)遞增子序列的一個(gè)變種，因?yàn)槊看魏戏ǖ那短资谴蟮奶仔〉?，相?dāng)于在二維平面中找一個(gè)最長(zhǎng)遞增的子序列，其長(zhǎng)度就是最多能嵌套的信封個(gè)數(shù)。

前面說(shuō)的標(biāo)準(zhǔn) LIS 算法只能在一維數(shù)組中尋找最長(zhǎng)子序列，而我們的信封是由 (w, h) 這樣的二維數(shù)對(duì)形式表示的，如何把 LIS 算法運(yùn)用過(guò)來(lái)呢？

讀者也許會(huì)想，通過(guò) w × h 計(jì)算面積，然后對(duì)面積進(jìn)行標(biāo)準(zhǔn)的 LIS 算法。但是稍加思考就會(huì)發(fā)現(xiàn)這樣不行，比如 1 × 10 大于 3 × 3，但是顯然這樣的兩個(gè)信封是無(wú)法互相嵌套的。

這道題的解法比較巧妙：

先對(duì)寬度 w 進(jìn)行升序排序，如果遇到 w 相同的情況，則按照高度 h 降序排序；之后把所有的 h 作為一個(gè)數(shù)組，在這個(gè)數(shù)組上計(jì)算 LIS 的長(zhǎng)度就是答案。

畫(huà)個(gè)圖理解一下，先對(duì)這些數(shù)對(duì)進(jìn)行排序：

然后在 h 上尋找最長(zhǎng)遞增子序列，這個(gè)子序列就是最優(yōu)的嵌套方案：

那么為什么這樣就可以找到可以互相嵌套的信封序列呢？稍微思考一下就明白了：

首先，對(duì)寬度 w 從小到大排序，確保了 w 這個(gè)維度可以互相嵌套，所以我們只需要專(zhuān)注高度 h 這個(gè)維度能夠互相嵌套即可。

其次，兩個(gè) w 相同的信封不能相互包含，所以對(duì)于寬度 w 相同的信封，對(duì)高度 h 進(jìn)行降序排序，保證二維 LIS 中不存在多個(gè) w 相同的信封（因?yàn)轭}目說(shuō)了長(zhǎng)寬相同也無(wú)法嵌套）。

下面看解法代碼：

// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
    int n = envelopes.length;
    // 按寬度升序排列，如果寬度一樣，則按高度降序排列
    Arrays.sort(envelopes, new Comparator<int[]>() 
    {
        public int compare(int[] a, int[] b) {
            return a[0] == b[0] ? 
                b[1] - a[1] : a[0] - b[0];
        }
    });
    // 對(duì)高度數(shù)組尋找 LIS
    int[] height = new int[n];
    for (int i = 0; i < n; i++)
        height[i] = envelopes[i][1];

    return lengthOfLIS(height);
}

int lengthOfLIS(int[] nums) {
    // 見(jiàn)前文
}

為了清晰，我將代碼分為了兩個(gè)函數(shù)， 你也可以合并，這樣可以節(jié)省下 height 數(shù)組的空間。

此處放上 Leetcode 官方答案，個(gè)人覺(jué)著解釋的更清晰一些：

根據(jù)題目的要求, 如果我們選擇了 $k$ 個(gè)信封, 它們的的寬度依次為 $w_0,w_1,?,w_{k?1}$, 高度依次為
$h_0,h_1,?,h_{k?1}$, 那么需要滿足: $$\{\begin{array}{l}{w}_0<w_1<?<w_{k?1}\\ h_0<h_1<?<h_{k?1}\end{array}$$
同時(shí)控制 $w$ 和 $h$ 兩個(gè)維度并不是那么容易, 因此我們考慮固定一個(gè)維度, 再在另一個(gè)維度上進(jìn)行選 擇。例如, 我們固定 $w$
維度, 那么我們將數(shù)組 envelopes 中的所有信封按照 $w$ 升序排序。這樣一 來(lái),
我們只要按照信封在數(shù)組中的出現(xiàn)順序依次進(jìn)行選取, 就一定保證滿足: $$w_0\le w_1\le ?\le w_{k?1}$$ 了。然而小于等于 $\le$ 和小于 $<$ 還是有區(qū)別的，但我們不妨首先考慮一個(gè)簡(jiǎn)化版本的問(wèn)題:
如果我們保證所有信封的 w 值互不相同, 那么我們可以設(shè)計(jì)出一種得到答案的方法嗎? 在 $w$ 值互不相同的前提下，小于等于 $\le$
和小于 $<$ 是等價(jià)的，那么我們?cè)谂判蚝?，就可以完全忽?$w$ 維度, 只需要考慮 $h$ 維度了。此時(shí), 我們需要解決的問(wèn)題即為:
給定一個(gè)序列, 我們需要找到一個(gè)最長(zhǎng)的子序列, 使得這個(gè)子序列中的元素嚴(yán)格單調(diào)遞增, 即上面 要求的:
$$h_0<h_1<?<h_{k?1}>$$ 那么這個(gè)問(wèn)題就是經(jīng)典的「最長(zhǎng)嚴(yán)格遞增子序列」問(wèn)題了, 讀者可以參考力扣平臺(tái)的 300 . 最長(zhǎng)遞增 子序列 及其 官方題解。最長(zhǎng)嚴(yán)格遞增子序列的詳細(xì)解決方法屬于解決本題的前置知識(shí)點(diǎn), 不是本文分析的重點(diǎn), 因此這里不再贅述,會(huì)在方法一和方法二中簡(jiǎn)單提及。 當(dāng)我們解決了簡(jiǎn)化版本的問(wèn)題之后, 我們來(lái)想一想使用上面的方法解決原問(wèn)題, 會(huì)產(chǎn)生什么錯(cuò)誤。當(dāng) $w$
值相同時(shí)，如果我們不規(guī)定 $h$ 值的排序順序，那么可能會(huì)有如下的情況： 排完序的結(jié)果為 $[(w,h)]=[(1,1),(1,2),(1,3),(1,4)]$, 由于這些信封的 $w$ 值都相同, 不存在一個(gè) 信封可以裝下另一個(gè)信封, 那么我們只能在其中選擇 1 個(gè)信封。然而如果我們完全忽略 $w$ 維度, 剩下的 $h$ 維度為 $[1,2,3,4]$,
這是一個(gè)嚴(yán)格遞增的序列, 那么我們就可以選擇所有的 4 個(gè)信封了, 這就產(chǎn)生了錯(cuò)誤。 因此，我們必須要保證對(duì)于每一種 $w$ 值，我們最多只能選擇 1 個(gè)信封。 我們可以將 $h$ 值作為排序的第二關(guān)鍵字進(jìn)行降序排序, 這樣一來(lái), 對(duì)于每一種 $w$ 值, 其對(duì)應(yīng)的信封 在排序后的數(shù)組中是按照 $h$ 值遞減的順序出現(xiàn)的, 那么這些 $h$ 值不可能組成長(zhǎng)度超過(guò) 1 的嚴(yán)格遞增的序列，這就從根本上杜絕了錯(cuò)誤的出現(xiàn)。 因此我們就可以得到解決本題需要的方法:

• 首先我們將所有的信封按照 $w$ 值第一關(guān)鍵字升序、 $h$ 值第二關(guān)鍵字降序進(jìn)行排序;
• 隨后我們就可以忽略 $w$ 維度, 求出 $h$ 維度的最長(zhǎng)嚴(yán)格遞增子序列, 其長(zhǎng)度即為答案。 下面簡(jiǎn)單提及兩種計(jì)算最長(zhǎng)嚴(yán)格遞增子序列的方法, 更詳細(xì)的請(qǐng)參考上文提到的題目以及對(duì)應(yīng)的官方 題解。

最后賦上個(gè)人題解：

    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        envelopes.sort(key = lambda x: (x[0], -x[1]))
        # heigth = [1] * len(envelopes)
        # for i in range(len(envelopes)):
        #     heigth[i] = envelopes[i][1]
        # return self.lcs(heigth)
        return self.lcsPro(envelopes)
    
    def lcs(self, heigth):
        if len(heigth) <= 1:
            return 1
        dp = [1] * len(heigth)
        for i in range(len(heigth)):
            for j in range(i):
                if heigth[i] > heigth[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)


    def lcsPro(self, envelopes):
        if len(envelopes) <= 1:
            return 1
        dp = [1] * len(envelopes)
        for i in range(len(envelopes)):
            for j in range(i):
                if envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp) ```

三、參考文獻(xiàn)

[1] 動(dòng)態(tài)規(guī)劃設(shè)計(jì)：最長(zhǎng)遞增子序列
[2] Leetcode 官方題解文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-648411.html

到了這里，關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)（二十三）動(dòng)態(tài)規(guī)劃設(shè)計(jì)：最長(zhǎng)遞增子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！