概述
DP，即動態規劃是解決最優化問題的一類算法，我們要通過將原始問題分解成規模更小的、相似的子問題，通過求解這些易求解的子問題來計算原始問題。
線性DP是一類基本DP，我們來通過它感受DP算法的奧義。
最長上升子序列（LIS）
LIS問題，即最長上升子序列問題，是指找到原始序列中最長的單調元素序列這些（這些元素在原始序列中不一定是挨在一起的）。
LeetCode 2521：
給你一個整數數組?
nums?，找到其中最長嚴格遞增子序列的長度。子序列?是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，
[3,6,2,7]?是數組?[0,3,1,6,2,2,7]?的子序列。示例 1：
輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。示例 2：
輸入：nums = [0,1,0,3,2,3] 輸出：4
思路
我們來找到規模更小的子問題。
對于本題來說，什么是規模更小的子問題？
如果在故事的最后我們希望找到整個數組的LIS，不妨先找到整個數組中更小規模的上升序列。
如果我們用稱可能的答案為一個狀態，那么我們需要兩個要素來表示這個狀態，一個是描述規模的范圍，一個描述這一段上升序列的長度。
那我們不妨定義?int dp[N]，其中dp[i] = num，表示從原始數組中以nums[i]結尾的LIS為num。
當我們未開始計算時，dp[i] = 1，因為至少nums[i]這一個元素算是一個長度為1的遞增子序列。
具體的，
const int n = nums.size(); // 獲取數組的長度
vector<int> dp(n, 1); // 考慮到n是一個運行期變量，我們使用vector現在，我們來求解dp[i] = ? 的子問題。
算法過程
每個子問題都要被求解，前提是比它小的問題被求解了，而不論大小規模，這些問題的求解過程是一樣的。
?求解DP問題，這被稱為狀態轉移，也就是我們從小規模的狀態推導出大規模的狀態。
對于下標i來說, dp[i] = dp[j] + 1，其中 j < i && nums[j] <?nums[i]，考慮到可能有多個j符合情況，我們取最大值。
從0計算到n - 1,當計算 i 時，j 一定計算過了，所以這是合理的。
直觀來說，我們需要一個二重循環：
for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++)if (nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);}Code
class Solution {
public:int lengthOfLIS(vector<int>& nums) {const int n = nums.size();vector<int> dp(n, 1);int ans = INT_MIN;for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++)if (nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);ans = max(ans, dp[i]);}return ans;}
};這種枚舉是O(n2)，怎么優化呢？?
優化方案
還記得二分查找嗎？
「數組」二分查找模版|二段性分析|恢復二段性 / LeetCode 35|33|81（C++）
有兩件事：
- LIS一定是單調的。
- 子問題LIS的起點越小、差分(LIS[i] - LIS[i - 1])越小，即上升越緩，越有利于后續的元素追加到末尾。
這兩件事很直觀，幾乎無須證明。
在遍歷到i時，我們不妨記錄當前LIS，然后這么做：
- 若nums[i]可以追加，則直接追加。
- 若nums[i]不可以追加，則二分找到LIS中當前大于nums[i]的元素，如果這個元素的上一個元素小于nums[i]，則用nums[i]替換這個元素，這就使得LIS的差分減小。
二分是由LIS的單調性保證的。
Code
class Solution {
public:int lengthOfLIS(vector<int>& nums) {const int n = nums.size();vector<int> LIS(n);int len = 0;for (int i = 0; i < n; i++)if (!len || nums[i] > LIS[len - 1])LIS[len++] = nums[i];else {auto pos = upper_bound(LIS.begin(), LIS.begin() + len, nums[i]);if(pos == LIS.begin() || *prev(pos) < nums[i])*pos = nums[i];}return len;}
}; 復雜度
時間復雜度:?O(nlogn)?//需求解n個狀態，每次求解通過二分進行。
空間復雜度:?O(n) ????????//預留dp數組空間
編輯距離
編輯距離，也稱為Levenshtein Distance，是衡量兩個字符串差異的一種度量方法。它定義為將一個字符串轉換成另一個字符串所需的最少編輯操作次數，包括插入、刪除和替換字符。編輯距離越小，兩個字符串越相似。
LeetCode 72：
給你兩個單詞?
word1?和?word2，?請返回將?word1?轉換成?word2?所使用的最少操作數??。你可以對一個單詞進行如下三種操作：
- 插入一個字符
- 刪除一個字符
- 替換一個字符
示例?1：
輸入：word1 = "horse", word2 = "ros" 輸出：3 解釋： horse -> rorse (將 'h' 替換為 'r') rorse -> rose (刪除 'r') rose -> ros (刪除 'e')示例?2：
輸入：word1 = "intention", word2 = "execution" 輸出：5 解釋： intention -> inention (刪除 't') inention -> enention (將 'i' 替換為 'e') enention -> exention (將 'n' 替換為 'x') exention -> exection (將 'n' 替換為 'c') exection -> execution (插入 'u')
思路
依舊要將原始問題處理成規模更小的子問題。
上一題倒是很爽，要存儲兩個信息，于是就用下標和值處理了，但這次我們需要三個信息，就需要二維數組了。
那我們不妨定義 `int dp[N][M]`，其中dp[i][j] = num，
表示從數組1中[1,? i]子數組與數組2中[1,? j]子數組的編輯距離為num。
做如下初始化：
for (int i = 1; i <= n; i++)dp[i][0] = i;
for (int j = 1; j <= m; j++)dp[0][j] = j;*注意*：dp[i]對應原始的word[i - 1]，我們從i = 1開始循環，即做了一格偏移，這是為了處理邊界，直觀來講，可以認為dp[i]代表原始數組的前i個字符。?
解題過程
我們能想到很直觀的二維循環。
有兩種可能：
- word[i] == word[j]，這是好事啊，編輯距離無需增加，dp[i][j] = dp[i - 1][j - 1];
- word[i] != word[j]，dp[i][j] 至少為 dp[i - 1][j - 1]，然后考慮：刪除/替換/插入，這三者不過都是讓二者相等的手段，我們只需要考慮之前的事，然后+1就行了。
- 考慮刪掉word1[i - 1]/在word2[j?- 1]后插入word1[i?- 1]，則dp[i][j] = dp[i - 1][j] + 1;
- 考慮刪掉word2[j - 1]/在word1[i - 1]后插入word2[j - 1]，則dp[i][j] = dp[i][j - 1] + 1;
- 考慮將word1[i - 1]替換為word2[j - 1]，則dp[i][j] = dp[i - 1][j - 1] + 1;
注意這里dp[i]對應word[i - 1]。
以上三者，取最大值：
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {dp[i][j] = dp[i - 1][j - 1];if (word1[i - 1] != word2[j - 1])dp[i][j] = min({dp[i][j], dp[i - 1][j], dp[i][j - 1]}) + 1;}計算 i 和 j 時，i - 1 和 j - 1一定計算過了，這是合法的。
Code
class Solution {
public:int minDistance(string word1, string word2) {const int n = word1.size(), m = word2.size();vector dp(n + 1, vector(m + 1, 0));for (int i = 1; i <= n; i++)dp[i][0] = i;for (int j = 1; j <= m; j++)dp[0][j] = j;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {dp[i][j] = dp[i - 1][j - 1];if (word1[i - 1] != word2[j - 1])dp[i][j] = min({dp[i][j], dp[i - 1][j], dp[i][j - 1]}) + 1;}return dp.back().back();}
};復雜度
時間復雜度:?O(nm)?//需求解n*m個狀態。
空間復雜度:?O(nm) //預留n*m個空間。
總結
線性dp的狀態轉移依靠的是非常直觀的線性增長的問題規模。
dp算法都是通過求解子問題進而求解原始問題的一類算法，希望你了解線性dp這類基本dp后有所體會。
