算法沉淀——動態規劃之兩個數組的 dp（上）（leetcode真題剖析）

在這里插入圖片描述

算法沉淀——動態規劃之兩個數組的 dp

01.最長公共子序列
02.不相交的線
03.不同的子序列
04.通配符匹配

01.最長公共子序列

題目鏈接：https://leetcode.cn/problems/longest-common-subsequence/

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。

一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。

示例 1：

輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長公共子序列是 "ace" ，它的長度為 3 。

示例 2：

輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長公共子序列是 "abc" ，它的長度為 3 。

示例 3：

輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個字符串沒有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 僅由小寫英文字符組成。

思路

狀態轉移方程：

如果當前字符相同（text1[i] == text2[j]），說明我們找到了一個新的公共字符，因此最長公共子序列的長度在之前的基礎上加 1：
- dp[i][j] = dp[i - 1][j - 1] + 1
如果當前字符不同（text1[i] != text2[j]），則我們需要考慮去掉 text1[i] 或者去掉 text2[j] 之后的最長公共子序列。這可以通過比較 text1 的前 i-1 個字符和 text2 的前 j 個字符的最長公共子序列長度，以及 text1 的前 i 個字符和 text2 的前 j-1 個字符的最長公共子序列長度，取最大值：
- dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

初始化：為了方便處理邊界情況，我們在文本 text1 和 text2 前各添加一個空字符，即 text1[0] 和 text2[0] 表示空串。這樣，dp 表的大小為 (m+1) x (n+1)，其中 m 和 n 分別是兩個文本的長度。初始化時，將第一行和第一列的值都設置為 0。

填表順序：最終的結果存儲在 dp[m][n] 中，其中 m 和 n 是兩個文本的長度。這個值表示 text1 和 text2 的最長公共子序列的長度。

代碼

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m=text1.size(),n=text2.size();text1=" "+text1,text2=" "+text2;vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)if(text1[i]==text2[j]) 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];}
};

02.不相交的線

題目鏈接：https://leetcode.cn/problems/uncrossed-lines/

在兩條獨立的水平線上按給定的順序寫下 nums1 和 nums2 中的整數。

現在，可以繪制一些連接兩個數字 nums1[i] 和 nums2[j] 的直線，這些直線需要同時滿足滿足：

nums1[i] == nums2[j]
且繪制的直線不與任何其他連線（非水平線）相交。

請注意，連線即使在端點也不能相交：每個數字只能屬于一條連線。

以這種方法繪制線條，并返回可以繪制的最大連線數。

示例 1：

輸入：nums1 = [1,4,2], nums2 = [1,2,4]
輸出：2
解釋：可以畫出兩條不交叉的線，如上圖所示。 
但無法畫出第三條不相交的直線，因為從 nums1[1]=4 到 nums2[2]=4 的直線將與從 nums1[2]=2 到 nums2[1]=2 的直線相交。

示例 2：

輸入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
輸出：3

示例 3：

輸入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
輸出：2

提示：

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

思路

如果我們希望確保兩條直線不相交，我們可以將問題轉化為在兩個整數數組中尋找最長的公共子序列。這是因為，如果兩條直線不相交，它們在同一列上對應的兩個元素在兩個數組中的順序關系應該保持一致。

這個問題可以用動態規劃來解決，具體步驟如下：

狀態表達：
- 我們選取兩個數組分別表示兩條直線，數組長度分別為 m 和 n。
- 定義狀態表 dp，其中 dp[i][j] 表示數組1的前 i 個元素和數組2的前 j 個元素中的最長公共子序列的長度。
狀態轉移方程：
- 如果 nums1[i] == nums2[j]，說明找到了一個公共元素，狀態轉移方程為 dp[i][j] = dp[i-1][j-1] + 1。
- 如果 nums1[i] != nums2[j]，則需要在兩個數組的前面部分分別尋找最長公共子序列，狀態轉移方程為 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始化：
- 為了方便處理邊界情況，可以在兩個數組的前面各添加一個虛擬元素，表示空串。
- 初始化 dp 數組的第一行和第一列為0，因為空串與任何數組的最長公共子序列長度都為0。
填表順序：
- 從上到下，從左到右填寫 dp 數組。
返回值：
- 最終的結果存儲在 dp[m][n] 中，表示兩個數組的最長公共子序列的長度。

代碼

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int m=nums1.size(),n=nums2.size();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)if(nums1[i-1]==nums2[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];}   
};

03.不同的子序列

題目鏈接：https://leetcode.cn/problems/distinct-subsequences/

你兩個字符串 s 和 t ，統計并返回在 s 的 子序列 中 t 出現的個數，結果需要對 109 + 7 取模。

示例 1：

輸入：s = "rabbbit", t = "rabbit"
輸出：3
解釋：
如下所示, 有 3 種可以從 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

輸入：s = "babgbag", t = "bag"
輸出：5
解釋：
如下所示, 有 5 種可以從 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母組成

思路

狀態表達：
- 選取第一個字符串 [0, i] 區間以及第二個字符串 [0, j] 區間作為研究對象，結合題目要求來定義狀態表達。
- 在這道題中，狀態表達為 dp[i][j]，表示在字符串 s 的 [0, j] 區間內的所有子序列中，有多少個 t 字符串 [0, i] 區間內的子串。
狀態轉移方程：
- 根據最后一個位置的元素，結合題目要求進行分類討論：
  - 當
```
t[i] == s[j]
```
    時：
    - 選擇 s[j] 作為結尾，相當于在狀態 dp[i-1][j-1] 中的所有符合要求的子序列的后面，再加上一個字符 s[j]，此時 dp[i][j] = dp[i-1][j-1]。
    - 不選擇 s[j] 作為結尾，相當于選擇了狀態 dp[i][j-1] 中所有符合要求的子序列，繼承了上個狀態里面的求得的子序列，此時 dp[i][j] = dp[i][j-1]。
  - 當
```
t[i] != s[j]
```
    時：
    - 子序列只能從 dp[i][j-1] 中選擇所有符合要求的子序列，繼承上個狀態里面求得的子序列，此時 dp[i][j] = dp[i][j-1]。
- 綜上，狀態轉移方程為：
  - 所有情況下都可以繼承上一次的結果：dp[i][j] = dp[i][j-1]。
  - 當 t[i] == s[j] 時，可以多選擇一種情況：dp[i][j] += dp[i-1][j-1]。
初始化：
- 引入空串后，方便初始化，注意下標的映射關系以及確保后續填表是正確的。
- 當 s 為空時，t 的子串中有一個空串和它一樣，因此初始化第一行全部為 1。
填表順序：
- 從上往下填每一行，每一行從左往右。
返回值：
- 根據狀態表達，返回 dp[m][n] 的值。

代碼

class Solution {
public:int numDistinct(string s, string t) {int m=t.size(),n=s.size();vector<vector<double>> dp(m+1,vector<double>(n+1));for(int j=0;j<=n;j++) dp[0][j]=1;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){dp[i][j]+=dp[i][j-1];if(t[i-1]==s[j-1]) dp[i][j]+=dp[i-1][j-1];}return dp[m][n];}
};

04.通配符匹配

題目鏈接：https://leetcode.cn/problems/wildcard-matching/

給你一個輸入字符串 (s) 和一個字符模式 (p) ，請你實現一個支持 '?' 和 '*' 匹配規則的通配符匹配：

'?' 可以匹配任何單個字符。
'*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要條件是：字符模式必須能夠 完全匹配 輸入字符串（而不是部分匹配）。

示例 1：

輸入：s = "aa", p = "a"
輸出：false
解釋："a" 無法匹配 "aa" 整個字符串。

示例 2：

輸入：s = "aa", p = "*"
輸出：true
解釋：'*' 可以匹配任意字符串。

示例 3：

輸入：s = "cb", p = "?a"
輸出：false
解釋：'?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。

提示：

0 <= s.length, p.length <= 2000
s 僅由小寫英文字母組成
p 僅由小寫英文字母、'?' 或 '*' 組成

思路

在處理兩個字符串之間的動態規劃問題時，通常按照以下步驟進行：

狀態表達：
- 選取第一個字符串 [0, i] 區間以及第二個字符串 [0, j] 區間作為研究對象，結合題目的要求定義狀態表達。
- 在這道題中，我們定義狀態表達為 dp[i][j]，表示字符串 p 的 [0, j] 區間內的子串能否匹配字符串 s 的 [0, i] 區間內的子串。
狀態轉移方程：
- 根據最后一個位置的元素，結合題目要求，進行分類討論：
  - 當 s[i] == p[j] 或 p[j] == '?' 時，兩個字符串匹配上了當前的一個字符，只能從 dp[i-1][j-1] 中看當前字符前面的兩個子串是否匹配，繼承上個狀態中的匹配結果，dp[i][j] = dp[i][j-1]。
  - 當 p[j] == '*' 時，匹配策略有兩種選擇：
    - 選擇 '*' 匹配空字符串，相當于它匹配了一個寂寞，直接繼承狀態 dp[i][j-1]，dp[i][j] = dp[i][j-1]。
    - 選擇 '*' 向前匹配 1 ~ n 個字符，直至匹配整個 s 串。相當于從 dp[k][j-1] (0 <= k <= i) 中所有匹配情況中，選擇性繼承可以成功的情況，dp[i][j] = dp[k][j-1] (0 <= k <= i)。
  - 當 p[j] 不是特殊字符且不與 s[i] 相等時，無法匹配。綜上，狀態轉移方程為：
    - 當 s[i] == p[j] 或 p[j] == '?' 時：dp[i][j] = dp[i-1][j-1]。
    - 當 p[j] == '*' 時，狀態轉移方程優化為：dp[i][j] = dp[i-1][j] || dp[i][j-1]。
初始化：
- dp 數組的值表示是否匹配，初始化整個數組為 false。
- 由于需要用到前一行和前一列的狀態，初始化第一行和第一列。
  - dp[0][0] 表示兩個空串是否匹配，初始化為 true。
  - 第一行表示 s 為空串，p 串與空串只有一種匹配可能，即 p 串表示為 "***"，此時也相當于空串匹配上空串，將所有前導為 "*" 的 p 子串與空串的 dp 值設為 true。
  - 第一列表示 p 為空串，不可能匹配上 s 串，跟隨數組初始化即可。
填表順序：
- 從上往下填每一行，每一行從左往右。
返回值：
- 根據狀態表達，返回 dp[m][n] 的值。

代碼

class Solution {
public:bool isMatch(string s, string p) {int m=s.size(),n=p.size();s=" "+s,p=" "+p;vector<vector<bool>> dp(m+1,vector<bool>(n+1));dp[0][0]=true;for(int i=1;i<=n;i++)if(p[i]=='*') dp[0][i]=true;else break;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){if(p[j]=='*') dp[i][j]=dp[i][j-1]||dp[i-1][j];else dp[i][j]=(p[j]=='?'||s[i]==p[j])&&dp[i-1][j-1];}return dp[m][n];}
};