想參考 DP LIS and LCS 的各種實戰題型的話，我有整理底家，刷起來！：

LeetCode - LIS Series LeetCode - LCS Series

LIS and LCS Note

題型	全名	輸入	目標
LIS	Longest Increasing Subsequence	一個序列	找最長遞增子序列
LCS	Longest Common Subsequence	兩個序列	找兩個序列共同的最長子序列

LIS：Longest Increasing Subsequence

LIS 核心思路

LIS 最重要的 DP 定義是：

dp[i] = 以 nums[i] 作為結尾的 LIS 長度

為什麼要定義成「以 nums[i] 結尾」？

因為要判斷 nums[i] 能不能接在前面的某個 subsequence 後面，必須知道前面那個 subsequence 的最後一個數字是什麼

如果 nums[j] < nums[i]，代表 nums[i] 可以接在 nums[j] 後面

因此狀態轉移是：
dp[i] = max(dp[i], dp[j] + 1);

條件是：
j < i && nums[j] < nums[i]

LIS 長度題

項目	說明
狀態定義	`dp[i] = 以 nums[i] 結尾的 LIS 長度`
初始化	`dp[i] = 1`
轉移條件	`nums[j] < nums[i]`
狀態轉移	`dp[i] = max(dp[i], dp[j] + 1)`
答案	`max(dp[i])`
時間複雜度	`O(n^2)`
空間複雜度	`O(n)`

注意答案不是 dp[n - 1]

因為 LIS 不一定以最後一個元素結尾，所以要取整個 dp array 的最大值

LIS O(n^2) 模板

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);

    int ans = 1;

    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;
}

LIS 計數題：O(n log n) 解法

LIS 還有一種 O(n log n) 解法，適合只求 LIS 長度

核心概念：

lisdp[i] = 長度為 i + 1 的遞增子序列中，最小可能的結尾值

結尾值越小越好，因為越容易接上後面的數字

LIS O(n log n) 模板

int lengthOfLIS(vector<int>& nums) {
    vector<int> lisdp;

    for (int x : nums) {
        auto it = lower_bound(lisdp.begin(), lisdp.end(), x);

        if (it == lisdp.end()) {
            lisdp.push_back(x);
        } else {
            *it = x;
        }
    }

    return lisdp.size();
}

lower_bound 和 upper_bound

題型	使用
嚴格遞增	`lower_bound`，找第一個 `>= x`
非嚴格遞增	`upper_bound`，找第一個 `> x`

嚴格遞增不能接受相等，所以遇到相同數字時，不能增加長度

LIS 計數題：Number of LIS

代表題目：

673. Number of Longest Increasing Subsequence

這題不是只問 LIS 長度，而是問：
有幾個最長遞增子序列
因此需要兩個 array：

陣列	意義
`len[i]`	以 `nums[i]` 結尾的 LIS 長度
`count[i]`	以 `nums[i]` 結尾，且長度為 `len[i]` 的 LIS 數量

初始化：

vector<int> len(n, 1);
vector<int> count(n, 1);

原因：

每個元素自己都可以形成長度為 1 的 LIS
每個元素自己形成 LIS 的方法數是 1

如果：nums[j] < nums[i]
代表 nums[i] 可以接在 nums[j] 後面
此時有兩種情況

情況一：找到更長的 LIS
原本以 i 結尾的最佳長度被更新了
既然找到更長的長度，原本較短的計數全部不重要，直接改成 count[j]

if (len[j] + 1 > len[i]) {
    len[i] = len[j] + 1;
    count[i] = count[j];
}

情況二：找到一樣長的 LIS
又找到另一批方法，也可以形成相同長度的 LIS
因此方法數要累加

else if (len[j] + 1 == len[i]) {
    count[i] += count[j];
}

LIS 計數模板

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();

    vector<int> len(n, 1);
    vector<int> count(n, 1);

    int maxLen = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                } else if (len[j] + 1 == len[i]) {
                    count[i] += count[j];
                }
            }
        }

        maxLen = max(maxLen, len[i]);
    }

    int ans = 0;

    for (int i = 0; i < n; ++i) {
        if (len[i] == maxLen) {
            ans += count[i];
        }
    }

    return ans;
}

LIS 計數模板重點

判斷	寫法	意義
找到更長的 LIS	`len[j] + 1 > len[i]`	更新長度，方法數覆蓋
找到一樣長的 LIS	`len[j] + 1 == len[i]`	長度不變，方法數累加
最後答案	加總所有 `len[i] == maxLen` 的 `count[i]`	LIS 不一定只結尾在某一個位置

LCS：Longest Common Subsequence

LCS 的核心問題是：

給兩個字串或序列，找出兩者共同的最長 subsequence 長度

例如：
text1 = “abcde”
text2 = “ace”

共同 subsequence 是：
“ace”

答案是 3

LCS 核心思路

LCS 是兩個序列之間的 DP

最常見的定義是：

dp[i][j] = text1 前 i 個字元和 text2 前 j 個字元的 LCS 長度

注意：

i 和 j 表示長度
目前比較的字元是 text1[i - 1] 和 text2[j - 1]

這樣定義可以避免處理 index 邊界問題，因為 dp[0][j] 和 dp[i][0] 都可以自然表示空字串

LCS DP 定義

項目	說明
狀態定義	`dp[i][j] = s1 前 i 個字元和 s2 前 j 個字元的 LCS 長度`
初始化	`dp[0][j] = 0`，`dp[i][0] = 0`
比較字元	`s1[i - 1]` 和 `s2[j - 1]`
答案	`dp[m][n]`
時間複雜度	`O(mn)`
空間複雜度	`O(mn)`

LCS 狀態轉移

情況一：兩個字元相同

如果：s1[i - 1] == s2[j - 1]

代表這個字元可以加入共同 subsequence

轉移：dp[i][j] = dp[i - 1][j - 1] + 1;

情況二：兩個字元不同

如果：s1[i - 1] != s2[j - 1]

代表這兩個字元不能一起選

有兩種選擇：

不選 s1[i - 1]
不選 s2[j - 1]

轉移dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

LCS 模板

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size();
    int n = s2.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

LIS 和 LCS 比較

項目	LIS	LCS
輸入	一個序列	兩個序列
目標	找最長遞增 subsequence	找兩個序列的最長共同 subsequence
DP 維度	一維	二維
狀態定義	`dp[i] = 以 nums[i] 結尾的 LIS 長度`	`dp[i][j] = s1 前 i 個和 s2 前 j 個的 LCS 長度`
轉移條件	`nums[j] < nums[i]`	`s1[i - 1] == s2[j - 1]`
答案位置	`max(dp[i])`	`dp[m][n]`
常見複雜度	`O(n^2)` 或 `O(n log n)`	`O(mn)`

題型判斷

LIS 題型特徵

看到以下關鍵字，通常可以往 LIS 思考：

increasing
decreasing
strictly increasing
subsequence
chain
pair chain
envelope
longest string chain

LIS 的本質：

在一個序列中，找出一條符合某種「可接續條件」的最長路徑

常見可接續條件：

數字變大
數字變小
pair 可以接在前一個 pair 後面
字串可以由前一個字串加一個字元形成

LCS 題型特徵

看到以下關鍵字，通常可以往 LCS 思考：

two strings
common subsequence
delete operation
make two strings same
uncrossed lines
minimum deletion
minimum ASCII delete sum

LCS 的本質：

在兩個序列中，找出共同保留下來的最長部分

經典題目

類型	題目	備註
LIS	300. Longest Increasing Subsequence	最標準 LIS，本題核心是 `dp[i] = 以 nums[i] 結尾的 LIS 長度`
LIS	673. Number of Longest Increasing Subsequence	LIS 數量題，同時維護 `len[i]` 與 `count[i]`，更長就覆蓋，一樣長就累加
LIS	674. Longest Continuous Increasing Subsequence	連續版 LIS，只能接前一個元素，核心是目前連續遞增長度 `cur`
LIS	354. Russian Doll Envelopes	二維 LIS，先排序 `width`，再對 `height` 做 LIS
LIS	368. Largest Divisible Subset	LIS-like DP，排序後條件從 `nums[j] < nums[i]` 改成 `nums[i] % nums[j] == 0`
LIS	646. Maximum Length of Pair Chain	LIS-like chain 題，條件是前一個 pair 的尾巴 `<` 下一個 pair 的開頭
LIS	1027. Longest Arithmetic Subsequence	LIS-like DP，需要多記一個公差 `diff`，狀態為 `dp[i][diff]`
LIS	1048. Longest String Chain	LIS-like DP，先依字串長度排序，判斷短字串是否能加一個字元變成長字串
LIS	2501. Longest Square Streak in an Array	LIS-like DP，條件是下一個數字等於前一個數字的平方，可用 `dp[x]` 記錄以 `x` 結尾的最長 streak
LCS	1143. Longest Common Subsequence	最標準 LCS，本題核心是 `dp[i][j] = text1 前 i 個與 text2 前 j 個的 LCS 長度`
LCS	1035. Uncrossed Lines	幾乎等同 LCS，只是把兩個字串換成兩個整數陣列
LCS	583. Delete Operation for Two Strings	LCS 應用，先求 LCS，答案為 `word1.size() + word2.size() - 2 * LCS`

Algorithm - DP LIS and LCS