當我們使用遞推的方式，來求解動態(tài)規(guī)劃時，我們會從 1 開始數(shù)起，一步步累加得到最終的狀態(tài)：
F(1) = 1
F(2) = F(1) + 1
...
F(N) = f(N-1) + 1
當我們使用遞歸的方式，來求解動態(tài)規(guī)劃時，我們會從把所有的鍵帽數(shù)量，記作狀態(tài) F(N)，當我們數(shù)了一個鍵帽后，那么 剩下的狀態(tài)就記作 F(N-1)，因此：
F(N) = F(N-1) + 1
F(N-1) = F(N-2) + 1
...
F(1) = 1
無論是遞推還是遞歸，都是得到的答案無疑都是一樣的，只不過思維的方式有些不一樣。遞推是正向思維，先有基礎(chǔ)答案后由復雜答案，最后得出最終問題的答案。遞歸是逆向思維，先有復雜的問題，然后把它化解為更簡單的問題，直到分解為能一眼看出答案的基本問題。
數(shù)鍵盤雖然是一個很簡單的游戲，但是解答的過程中已經(jīng)包含了最基礎(chǔ)的動態(tài)規(guī)劃解題思路：
定義狀態(tài)
再重新定義問題
找到最基礎(chǔ)的狀態(tài)
找出狀態(tài)轉(zhuǎn)移方程
編程求解
最長上升子序列
問：給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例：
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
說明：
可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。
你算法的時間復雜度應該為 O(n2) 。
這道題目的問題是，求最長上升子序列的長度。直接拿到這個問題，肯定一臉懵逼，最長上升子序列的長度是什么？斷詞斷句一個個解釋，序列、子序列、上升序列、最長上升子序列的長度。
序列：這里指的是，一個無序的整數(shù)數(shù)組。
子序列：將原序列中的部分值，重新組合成一個新的序列，這個新的序列就是子序列。一個序列可以有多個子序列。如，原序列 [1, 5, 2, 3]，那么 [1, 5] 和 [1, 2, 3] 都是原序列的子序列。
上升序列：從前往后看，序列中的前面的數(shù)字比后面的數(shù)字更小，序列呈遞增規(guī)律，就是上升序列。[1, 2, 3] 就是上升序列，[1,2,0] 就不是上升序列。
最長上升子序列的長度：一個序列可能會有多個上升子序列，其中長度最長的叫做最長上升子序列，其長度叫做最長上升子序列的長度。
動態(tài)規(guī)劃方法一
第一步：定義狀態(tài)。定義狀態(tài)為，以當前序列第 i 個數(shù)字結(jié)尾的最長上升子序列的長度，記作 L(i)，0≤i≤N-1，N為序列長度。示例：序列[1,2,3]，狀態(tài) L[1] = 2 ，表示第 1 個以 2 結(jié)尾的最長上升子序列的長度為 2。
第二步：重新定位問題。序列中的最長上升子序列，不一定是以最后一個數(shù)字結(jié)尾，而是所有狀態(tài)中的最大值，即 Math.max(L[0],L[1],…,L(N-1))。示例：[1,2,0] 的最長上升子序列是 [1,2] ，是以第1個數(shù)字結(jié)尾的。
第三步：找到最基礎(chǔ)的狀態(tài)。當序列為空時，結(jié)尾的最長上升子序列的長度為0。但是我們發(fā)現(xiàn)，最初我們定義的狀態(tài)，并不能表示該最基礎(chǔ)的狀態(tài)，因此需要對狀態(tài)的定義稍作修正。
狀態(tài)：以當前序列第 index 個數(shù)字結(jié)尾的最長上升子序列的長度，index 是序列的下標，記 i = index + 1 ，狀態(tài)為 L(i)，0≤i≤N，N為序列長度。此時 L[0] 表示空序列的最長上升子序列的長度 L[0] = 0，L[1] 表示以序列中第 0 位數(shù)字結(jié)尾的最長上升子序列的長度，L[1] = 1。
第四步：找到狀態(tài)轉(zhuǎn)移方程。若 L[i] 大于 1，則 L[i] 表示的子序列，去掉最后一位數(shù)，依舊是一個子序列，記該子序列為 L[j] 。其關(guān)系為 L[i] = L[j] + 1 。其中 L[j] 的最后一位 nums[j -1] < nums[i - 1]，且 L[j] = Math.max( L[1],…,L[i-1]) ，0
例如：序列A [1, 2, 6, 3, 4]
1. L[0] = 0
2. L[1] = 1
3. L[2] = Math.max( L[1]) + 1 = L[1] + 1 = 2, 其中 nums[1-1] < nums[2-1]
4. L[3] = Math.max(L[1], L[2]) + 1 = L[2] + 1 = 2, 其中 nums[2-1] < nums[3-1]
5. L[4] = Math.max(L[1], L[2],L[3]) + 1 = L[2] + 1 = 2, 其中 nums[2-1] < nums[4-1]
6. L[5] = Math.max(L[1], L[2],L[3],L[4]) + 1 = L[4] + 1 = 2, 其中 nums[4-1] < nums[5-1]
變成為：
function lengthOfLIS(nums) {
const dp = [0]
for (let i = 1; i <= nums.length; i++) {
let max = 0
for (let j = 1; j < i; j++) {
if (nums[j - 1] < nums[i - 1]) {
max = Math.max(max, dp[j])
}
}
dp[i] = max + 1
}
return Math.max(...dp)
};
動態(tài)規(guī)劃方法二
第一步：定義狀態(tài)。在序列前 index 項中，所有可能成為最長上升子序列的子序列。S[i]
示例：A [10, 1, 12, 2, 3]
S[0] = [[10]]
S[1] = [[10], [1]]
S[2] = [[10, 12], [1, 12]]
S[3] = [[10, 12], [1, 12], [1, 2]]
S[4] = [[10, 12], [1, 12], [1, 2, 3]]
當 S[1] = [[10], [1]] 時，A[2] 存在三種情況，①當 10 < A[2] 時， [10, A[2]] 和 [1, A[2]] 表示的長度等價；②當 1 < A[2] ≤ 10 時， [1, A[2]] 比 [10] 長；③當 A[2] ≤ 1 時，S[3] = [[10], [1], A[3]]。
因為題目只需要返回最終長度，所以 [10] 或 [1] 兩種情況實際，可以簡寫為 [1] 這一種情況。A[3] 存在 3中情況，分別為①當 10 < A[2] 時， [1, A[2]] ；②當 1 < A[2] ≤ 10 時， [1, A[2]]；③當 A[2] ≤ 1 時，S[3] = [A[3]]。因此可證明，只保留 [1] 一種情況，實際上已經(jīng)代表了 [10] 或 [1] 兩種情況。
對狀態(tài)進行重新定義：在序列前 i 項中，長度為 k 的上升子序列中，最后一位的最小值。S[i]
示例：A [10, 1, 12, 2, 3]
S[0] = [10]
S[1] = [1]
S[2] = [1,12]
S[3] = [1,2]
S[4] = [1,2,3]
第二步：重新定位問題。 求 S[N-1] 的長度，其中 N 為序列的長度。
第三步：找到最基礎(chǔ)的狀態(tài)。當序列為空時，結(jié)尾的最長上升子序列的長度為0，因此對問題和狀態(tài)進行重新修正。
狀態(tài)：在序列前 i + 1 項中，長度為 k 的上升子序列中，最后一位的最小值。S[i]
問題：求 S[N] 的長度，其中 N 為序列的長度。
第四步：找到狀態(tài)轉(zhuǎn)移方程。如果 A[i-1] 比 S[i] 最后一位還要大，記作 S[i][len -1] < A[i-1] ，即可以組成一個更長子序列，s[i] = [...s[i -1],A[i-1]]。如果 A[i-1] 比 S[i] 中某一位 S[i][j]要小，但是比該位的前一位 S[i][j-1]要大，更具第一步中的推論，可以用 A[i-1] 替換掉 S[i][j] ，S[i] = […,S[i][j-1],A[i-1] ,…]
示例：A [10, 1, 12, 2, 3]
S[0] = [] // 初始化
S[1] = [10] // 在最后添加 A[1-1]=10
S[2] = [1] // A[2-1] < S[2][0]，因此替換掉 S[2][0]
S[3] = [1,12] // 在最后添加 A[3-1]= 12
S[4] = [1,2] // S[2][0] < A[2-1] < S[2][1]，因此替換掉 S[2][1]
S[5] = [1,2,3] // 在最后添加 A[5-1]= 3
實現(xiàn)：
function lengthOfLIS(nums) {
const sequence = []
// 復雜度 n
for (let i = 1; i <= nums.length; i++) {
let len = sequence.length
// 增加
if (sequence[len - 1] < nums[i-1]) {
sequence[len] = nums[i-1]
// 替換
} else {
// sequence 具有單調(diào)性，可以使用 logn 復雜度的二分查找，查找到 S[i][j-1]
