讀完本文，你可以去力扣拿下如下題目：
-----------
也許有讀者看了前文 動態(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)，我們通過一種簡單的紙牌游戲來輔助理解這種巧妙的解法。
先看一下題目，很容易理解：
注意「子序列」和「子串」這兩個名詞的區(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ù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
舉兩個例子：
算法演進的過程是這樣的，：
根據(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)庋劭闯鰜淼?，我們應該怎么設計算法邏輯來正確計算每個 dp[i] 呢？
這就是動態(tài)規(guī)劃的重頭戲了，要思考如何設計算法邏輯進行狀態(tài)轉(zhuǎn)移，才能正確運行呢？這里就可以使用數(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] 的值即可。
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)?？偨Y一下如何找到動態(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í)幚磉@些撲克牌，最終要把這些牌分成若干堆。
處理這些撲克牌要遵循以下規(guī)則：
只能把點數(shù)小的牌壓到點數(shù)比它大的牌上；如果當前牌點數(shù)較大沒有可以放置的堆，則新建一個堆，把這張牌放進去；如果當前牌有多個堆可供選擇，則選擇最左邊的那一堆放置。
比如說上述的撲克牌最終會被分成這樣 5 堆（我們認為紙牌 A 的牌面是最大的，紙牌 2 的牌面是最小的）。
為什么遇到多個可選擇堆的時候要放到最左邊的堆上呢？因為這樣可以保證牌堆頂?shù)呐朴行颍?, 4, 7, 8, Q），證明略。
按照上述規(guī)則執(zhí)行，可以算出最長遞增子序列，牌的堆數(shù)就是最長遞增子序列的長度，證明略。
我們只要把處理撲克牌的過程編程寫出來即可。每次處理一張撲克牌不是要找一個合適的牌堆頂來放嗎，牌堆頂?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)的推演轉(zhuǎn)移，最終得到答案。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標星！
