讀完本文，你可以去力扣拿下如下題目：
-----------
也許有讀者看了前文 動(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)輔助理解這種巧妙的解法。
先看一下題目，很容易理解：
注意「子序列」和「子串」這兩個(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)度。
PS：為什么這樣定義呢？這是解決子序列問(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)遞增子序列起碼要包含它自己。
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚(yú)得水了。
舉兩個(gè)例子：
算法演進(jìn)的過(guò)程是這樣的，：
根據(jù)這個(gè)定義，我們的最終結(jié)果（子序列的最大長(zhǎng)度）應(yīng)該是 dp 數(shù)組中的最大值。
int res = 0;
for (int i = 0; i < dp.size(); 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)度加一。
顯然，可能形成很多種新的子序列，但是我們只選擇最長(zhǎng)的那一個(gè)，把最長(zhǎng)子序列的長(zhǎng)度作為 dp[5] 的值即可。
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++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
結(jié)合我們剛才說(shuō)的 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;
}
至此，這道題就解決了，時(shí)間復(fù)雜度 O(N^2)?？偨Y(jié)一下如何找到動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移關(guān)系：
1、明確 dp 數(shù)組所存數(shù)據(jù)的含義。這一步對(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ù)組。
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚(yú)得水了。
二、二分查找解法
這個(gè)解法的時(shí)間復(fù)雜度為 O(NlogN)，但是說(shuō)實(shí)話(huà)，正常人基本想不到這種解法（也許玩過(guò)某些紙牌游戲的人可以想出來(lái)）。所以大家了解一下就好，正常情況下能夠給出動(dòng)態(tài)規(guī)劃解法就已經(jīng)很不錯(cuò)了。
根據(jù)題目的意思，我都很難想象這個(gè)問(wèn)題竟然能和二分查找扯上關(guān)系。其實(shí)最長(zhǎng)遞增子序列和一種叫做 patience game 的紙牌游戲有關(guān)，甚至有一種排序方法就叫做 patience sorting（耐心排序）。
為了簡(jiǎn)單起見(jiàn)，后文跳過(guò)所有數(shù)學(xué)證明，通過(guò)一個(gè)簡(jiǎn)化的例子來(lái)理解一下算法思路。
首先，給你一排撲克牌，我們像遍歷數(shù)組那樣從左到右一張一張?zhí)幚磉@些撲克牌，最終要把這些牌分成若干堆。
處理這些撲克牌要遵循以下規(guī)則：
只能把點(diǎn)數(shù)小的牌壓到點(diǎn)數(shù)比它大的牌上；如果當(dāng)前牌點(diǎn)數(shù)較大沒(méi)有可以放置的堆，則新建一個(gè)堆，把這張牌放進(jìn)去；如果當(dāng)前牌有多個(gè)堆可供選擇，則選擇最左邊的那一堆放置。
比如說(shuō)上述的撲克牌最終會(huì)被分成這樣 5 堆（我們認(rèn)為紙牌 A 的牌面是最大的，紙牌 2 的牌面是最小的）。
為什么遇到多個(gè)可選擇堆的時(shí)候要放到最左邊的堆上呢？因?yàn)檫@樣可以保證牌堆頂?shù)呐朴行颍?, 4, 7, 8, Q），證明略。
按照上述規(guī)則執(zhí)行，可以算出最長(zhǎng)遞增子序列，牌的堆數(shù)就是最長(zhǎng)遞增子序列的長(zhǎng)度，證明略。
我們只要把處理?yè)淇伺频倪^(guò)程編程寫(xiě)出來(lái)即可。每次處理一張撲克牌不是要找一個(gè)合適的牌堆頂來(lái)放嗎，牌堆頂?shù)呐撇皇?strong>有序嗎，這就能用到二分查找了：用二分查找來(lái)搜索當(dāng)前牌應(yīng)放置的位置。
PS：舊文二分查找算法詳解詳細(xì)介紹了二分查找的細(xì)節(jié)及變體，這里就完美應(yīng)用上了，如果沒(méi)讀過(guò)強(qiáng)烈建議閱讀。
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;
}
}
/*********************************/
// 沒(méi)找到合適的牌堆，新建一堆
if (left == piles) piles++;
// 把這張牌放到牌堆頂
top[left] = poker;
}
// 牌堆數(shù)就是 LIS 長(zhǎng)度
return piles;
}
至此，二分查找的解法也講解完畢。
這個(gè)解法確實(shí)很難想到。首先涉及數(shù)學(xué)證明，誰(shuí)能想到按照這些規(guī)則執(zhí)行，就能得到最長(zhǎng)遞增子序列呢？其次還有二分查找的運(yùn)用，要是對(duì)二分查找的細(xì)節(jié)不清楚，給了思路也很難寫(xiě)對(duì)。
所以，這個(gè)方法作為思維拓展好了。但動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法應(yīng)該完全理解：假設(shè)之前的答案已知，利用數(shù)學(xué)歸納的思想正確進(jìn)行狀態(tài)的推演轉(zhuǎn)移，最終得到答案。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線(xiàn)電子書(shū) 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉(cāng)庫(kù) 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
