---

前言

問題本質
它主要圍繞著給定的兩個數組展開，旨在通過對這兩個數組元素間關系的分析，找出滿足特定目標的最優解。比如在字符串處理中，兩個字符串可看作字符數組，求它們的最長公共子序列等問題；或是在數值數組場景下，計算從兩個數組元素組合中得到的最大收益等。
解題關鍵要素
狀態定義：通常構建一個二維數組 dp[i][j] 作為狀態表示。這里的 i 對應第一個數組的下標，j 對應第二個數組的下標 。dp[i][j] 代表在考慮第一個數組前 i 個元素和第二個數組前 j 個元素時，問題的最優解值，像上述最長公共子序列問題中，dp[i][j] 就表示對應前綴子串的最長公共子序列長度。
狀態轉移方程：這是解決問題的核心。需深入剖析問題特性，明確 dp[i][j] 如何由已求解的子問題狀態（如 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1] 等）推導得出。例如在求兩個數組元素匹配的最大得分問題中，若當前兩個數組元素匹配，dp[i][j] 可能由 dp[i - 1][j - 1] 加上對應得分轉移而來；若不匹配，則需比較 dp[i - 1][j] 和 dp[i][j - 1] 取較大值。
邊界條件：初始化 dp 數組的第一行和第一列。如在最長公共子序列問題里，dp[0][j] 和 dp[i][0] 都初始化為 0 ，因為一個空串與另一個串不存在公共子序列。
通過合理定義狀態、精準推導狀態轉移方程并正確處理邊界條件，就能借助動態規劃高效解決涉及兩個數組的各類問題。

下面本篇文章，將通過例題為大家詳細動態規劃中的兩個數組的dp問題！

例題

一、最長公共子序列

1. 題目鏈接：最長公共子序列
2. 題目描述：

給定兩個字符串 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 僅由?寫英?字符組成。

3. 解法（動態規劃）：
   算法思路：
   狀態表示： 對于兩個數組的動態規劃，我們的定義狀態表?的經驗就是：
   i. 選取第?個數組 [0, i] 區間以及第?個數組 [0, j] 區間作為研究對象；
   ii. 結合題目要求，定義狀態表?。 在這道題中，我們根據定義狀態表示為：
   dp[i][j] 表示： s1 的 [0, i] 區間以及 s2 的 [0, j] 區間內的所有的子序列中，最長公共子序列的長度。
   狀態轉移方程： 分析狀態轉移方程的經驗就是根據「最后?個位置」的狀況，分情況討論。 對于 dp[i][j] ，我們可以根據 s1[i] 與 s2[j] 的字符分情況討論：
   i. 兩個字符相同， s1[i] = s2[j] ：那么最長公共子序列就在 s1 的 [0, i - 1] 以 及 s2 的 [0, j - 1] 區間上找到?個最長的，然后再加上 s1[i] 即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 ；
   ii. 兩個字符不相同， s1[i] != s2[j] ：那么最長公共子序列?定不會同時以 s1[i]
   和 s2[j] 結尾。那么我們找最?公共?序列時，有下面三種策略：
   ? 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 區間內找：此時最??度為 dp[i - 1][j] ； ? 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 區間內找：此時最大長度為 dp[i][j - 1] ；
   ? 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 區間內找：此時最大長度為dp[i - 1][j - 1] 。 我們要三者的最大值即可。但是我們細細觀察會發現，第三種包含在第?種和第二種情況里面，但是我們求的是最大值，并不影響最終結果。因此只需求前兩種情況下的最大值即可。 綜上，狀態轉移方程為：
   if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
   if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。
   初始化：
   a. 「空串」是有研究意義的，因此我們將原始 dp 表的規模多加上??和?列，表?空串。
   b. 引入空串后，大大的方便我們的初始化。
   c. 但也要注意「下標的映射關系」，以及??的值要「保證后續填表是正確的」。
   當 s1 為空時，沒有長度，同理 s2 也是。因此第??和第?列里面的值初始化為 0 即可保證后續填表是正確的。
   填表順序： 根據「狀態轉移方程」得：從上往下填寫每?行，每?行從左往右。
   返回值： 根據「狀態表示」得：返回 dp[m][n]

4. 代碼示例：

 public int longestCommonSubsequence(String s1, String s2) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = s1.length(), n = s2.length();s1 = " " + s1;s2 = " " + s2;int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)if (s1.charAt(i) == s2.charAt(j))dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);return dp[m][n];}

二、不相交的線

1. 題目鏈接：不相交的線
2. 題目描述：

在兩條獨立的水平線上按給定的順序寫下 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

3. 解法（動態規劃）：
   算法思路： 如果要保證兩條直線不相交，那么我們「下?個連線」必須在「上?個連線」對應的兩個元素的 「后面」尋找相同的元素。這不就轉化成「最長公共子序列」的模型了嘛。那就是在這兩個數組中 尋找「最長的公共子序列」。
   只不過是在整數數組中做?次「最長的公共子序列」，代碼幾乎?模?樣，這里就不再贅述算法原理啦~

4. 代碼示例：

 public int maxUncrossedLines(int[] nums1, int[] nums2) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = nums1.length, n = nums2.length;int[][] dp = new int[m + 1][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] = Math.max(dp[i - 1][j], dp[i][j - 1]);return dp[m][n];}

三、不同的子序列

1. 題目鏈接：不同的子序列
2. 題目描述：

給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現的個數。 字符串的?個子序列是指，通過刪除?些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串。（例如，“ACE” 是 “ABCDE” 的?個子序列，而 “AEC” 不是） 題目數據保證答案符合 32 位帶符號整數范圍。
示例 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

3. 解法（動態規劃）： 算法思路：
   狀態表示： 對于兩個字符串之間的 dp 問題，我們?般的思考方式如下：
   i. 選取第?個字符串的 [0, i] 區間以及第?個字符串的 [0, j] 區間當成研究對象，結 合題目的要求來定義「狀態表示」；
   ii. 然后根據兩個區間上「最后?個位置的字符」，來進行「分類討論」，從而確定「狀態轉移方程」。
   我們可以根據上面的策略，解決大部分關于兩個字符串之間的 dp 問題。
   dp[i][j] 表示：在字符串 s 的 [0, j] 區間內的所有子序列中，有多少個 t 字符串 [0,
   i] 區間內的子串。
   狀態轉移方程： 老規矩，根據「最后?個位置」的元素，結合題目要求，分情況討論：
   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] 時的結果。
   ii. 當 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]
   初始化：
   a. 「空串」是有研究意義的，因此我們將原始 dp 表的規模多加上??和?列，表?空串。
   b. 引?空串后，??的?便我們的初始化。
   c. 但也要注意「下標的映射關系」，以及??的值要「保證后續填表是正確的」。
   當 s 為空時， t 的子串中有?個空串和它?樣，因此初始化第??全部為 1 。
   填表順序： 「從上往下」填每?行，每?行「從左往右」。
   返回值：根據「狀態表?」，返回 dp[m][n] 的值。

4. 代碼示例：

 public int numDistinct(String s, String t) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = t.length(), n = s.length();int[][] dp = new int[m + 1][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.charAt(i - 1) == s.charAt(j - 1))dp[i][j] += dp[i - 1][j - 1];}return dp[m][n];}

四、通配符匹配

1. 題目鏈接：通配符匹配
2. 題目描述：

給定?個字符串 (s) 和?個字符模式 § ，實現?個?持 ‘?’ 和 ’ * ’ 的通配符匹配。
‘?’ 可以匹配任何單個字符。
’ * ’ 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。 說明: s 可能為空，且只包含從 a-z 的小寫字母。 p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 。
示例 1:
輸?: s = “aa” p = “a” 輸出: false
解釋: “a” 無法匹配 “aa” 整個字符串。
示例 2:
輸入: s = “aa” p = ""
輸出: true
解釋: ‘’ 可以匹配任意字符串。
示例 3:
輸入: s = “cb” p = “?a” 輸出: false
解釋: ‘?’ 可以匹配 ‘c’, 但第?個 ‘a’ ?法匹配 ‘b’。 ?例 4:
輸入: s = “adceb” p = “ab” 輸出: true
解釋: 第?個 '’ 可以匹配空字符串, 第?個 '’ 可以匹配字符串 “dce”. ?例 5:
輸?: s = “acdcb” p = "ac?b" 輸出: false

3. 解法（動態規劃）：
   算法思路：
   狀態表示： 對于兩個字符串之間的 dp 問題，我們?般的思考?式如下：
   i. 選取第?個字符串的 [0, i] 區間以及第二個字符串的 [0, j] 區間當成研究對象，結合題目的要求來定義「狀態表示」；
   ii. 然后根據兩個區間上「最后?個位置的字符」，來進行「分類討論」，從而確定「狀態轉移方程」。
   我們可以根據上?的策略，解決大部分關于兩個字符串之間的 dp 問題。 因此，我們定義狀態表示為：
   dp[i][j] 表示： p 字符串 [0, j] 區間內的子串能否匹配字符串 s 的 [0, i] 區間內的 ?串。
   狀態轉移方程： 老規矩，根據最后?個位置的元素，結合題目要求，分情況討論：
   i. 當 s[i] == p[j] 或 p[j] == ‘?’ 的時候，此時兩個字符串匹配上了當前的?個字 符，只能從 dp[i - 1][j - 1] 中看當前字符前?的兩個子串是否匹配。只能繼承上個狀態中的匹配結果， dp[i][j] = dp[i][j - 1] ；
   ii. 當 p[j] == ‘’ 的時候，此時匹配策略有兩種選擇：
   ? ?種選擇是： * 匹配空字符串，此時相當于它匹配了?個寂寞，直接繼承狀態 dp[i][j - 1] ，此時 dp[i][j] = dp[i][j - 1] ；
   ? 另?種選擇是： * 向前匹配 1 ~ n 個字符，直?匹配上整個 s1 串。此時相當于 從 dp[k][j - 1] (0 <= k <= i) 中所有匹配情況中，選擇性繼承可以成功的 情況。此時 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；
   iii. 當 p[j] 不是特殊字符，且不與 s[i] 相等時，無法匹配。 三種情況加起來，就是所有可能的匹配結果。 綜上所述，狀態轉移?程為： ? 當 s[i] == p[j] 或 p[j] == ‘?’ 時： dp[i][j] = dp[i][j - 1] ； ? 當 p[j] == '’ 時，有多種情況需要討論： dp[i][j] = dp[k][j - 1] (0 <= k <= i) ； 優化：當我們發現，計算?個狀態的時候，需要?個循環才能搞定的時候，我們要想到去優化。優 化的?向就是用?個或者兩個狀態來表示這?堆的狀態。通常就是把它寫下來，然后?數學的方式 做?下等價替換： 當 p[j] == '’ 時，狀態轉移方程為：dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] …
   我們發現 i 是有規律的減小的，因此我們去看看 dp[i - 1][j] ：dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] …
   我們驚奇的發現， dp[i][j] 的狀態轉移?程??除了第?項以外，其余的都可以用 dp[i - 1][j] 替代。因此，我們優化我們的狀態轉移?程為： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。
   初始化： 由于 dp 數組的值設置為是否匹配，為了不與答案值混淆，我們需要將整個數組初始化為
   false 。 由于需要用到前一行和前一列的狀態，我們初始化第一行、第?列即可。
   ? dp[0][0] 表?兩個空串能否匹配，答案是顯然的， 初始化為 true 。
   ? 第一行表示 s 是?個空串， p 串和空串只有?種匹配可能，即 p 串表示為 "*" ，此時 也相當于空串匹配上空串。所以，我們可以遍歷 p 串，把所有前導為 "" 的 p ?串和空串 的 dp 值設為 true 。 ? 第?列表示p 是?個空串，不可能匹配上 s 串，跟隨數組初始化即可。
   填表順序：
   從上往下填每一行，每?行從左往右。
   返回值： 根據狀態表示，返回 dp[m][n] 的值。

4. 代碼示例

 public boolean isMatch(String ss, String pp) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回結果int m = ss.length(), n = pp.length();ss = " " + ss;pp = " " + pp;char[] s = ss.toCharArray();char[] p = pp.toCharArray();boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;for (int j = 1; j <= n; j++)if (p[j] == '*') dp[0][j] = 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 - 1][j] || dp[i][j - 1];elsedp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i - 1][j -1];return dp[m][n];}

五、交錯字符串

1. 題目鏈接：
2. 題目描述：

給定三個字符串 s1、s2、s3，請你幫忙驗證 s3 是否是由 s1 和 s2 交錯組成的。
兩個字符串 s 和 t 交錯 的定義與過程如下，其中每個字符串都會被分割成若干非空子字符串： s = s1 + s2 + … + sn
t = t1 + t2 + … + tm |n - m| <= 1 交錯 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味著字符串 a 和 b 連接。
示例 1：

輸?：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” 輸出：true
示例 2：輸入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
輸出：false
示例 3：輸入：s1 = “”, s2 = “”, s3 = “”
輸出：true

3. 解法（動態規劃）： 算法思路： 對于兩個字符串之間的 dp 問題，我們?般的思考?式如下：
   i. 選取第?個字符串的 [0, i] 區間以及第?個字符串的 [0, j] 區間當成研究對象，結 合題?的要求來定義「狀態表?」；
   ii. 然后根據兩個區間上「最后?個位置的字符」，來進?「分類討論」，從?確定「狀態轉移 ?程」。
   我們可以根據上?的策略，解決?部分關于兩個字符串之間的 dp 問題。
   這道題??空串是有研究意義的，因此我們先預處理?下原始字符串，前?統?加上?個占位符：
   s1 = " " + s1, s2 = " " + s2, s3 = " " + s3 。
   狀態表?：
   dp[i][j] 表?字符串 s1 中 [1, i] 區間內的字符串以及 s2 中 [1, j] 區間內的字符 串，能否拼接成 s3 中 [1, i + j] 區間內的字符串。
   狀態轉移?程： 先分析?下題目，題目中交錯后的字符串為 s1 + t1 + s2 + t2 + s3 + t3… ，看 似?個 s ?個 t 。實際上 s1 能夠拆分成更小的?個字符，進而可以細化成 s1 + s2 + s3 + t1 + t2 + s4… 。 也就是說，并不是前?個用了 s 的子串，后?個必須要用 t 的子串。這?點理解，對我們的狀態轉移很重要。
   繼續根據兩個區間上「最后?個位置的字符」，結合題目的要求，來進行「分類討論」：
   i. 當 s3[i + j] = s1[i] 的時候，說明交錯后的字符串的最后?個字符和 s1 的最后? 個字符匹配了。那么整個字符串能否交錯組成，變成：s1 中 [1, i - 1] 區間上的字符串以及 s2 中 [1, j] 區間上的字符串，能夠交 錯形成 s3 中 [1, i + j - 1] 區間上的字符串，也就是 dp[i - 1][j]；此時 dp[i][j] = dp[i - 1][j]
   ii. 當 s3[i + j] = s2[j] 的時候，說明交錯后的字符串的最后?個字符和 s2 的最后 ?個字符匹配了。那么整個字符串能否交錯組成，變成：s1 中 [1, i] 區間上的字符串以及 s2 中 [1, j - 1] 區間上的字符串，能夠交 錯形成 s3 中 [1, i + j - 1] 區間上的字符串，也就是 dp[i][j - 1] ；
   iii. 當兩者的末尾都不等于 s3 最后?個位置的字符時，說明不可能是兩者的交錯字符串。 上述三種情況下，只要有?個情況下能夠交錯組成目標串，就可以返回 true 。因此，我們可以定義狀態轉移為：
   dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1])
   只要有?個成立，結果就是 true 。
   初始化： 由于用到 i - 1 , j - 1 位置的值，因此需要初始化「第?個位置」以及「第?行」和「第? 列」。
   ? 第?個位置：
   dp[0][0] = true ，因為空串 + 空串能夠構成?個空串。
   ? 第?行： 第?行表示 s1 是?個空串，我們只用考慮 s2 即可。因此狀態轉移之和 s2 有關：
   dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1] ， j 從 1 到 n （ n 為 s2 的?度） ? 第?列： 第?列表? s2 是?個空串，我們只?考慮 s1 即可。因此狀態轉移之和 s1 有關：
   dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0] ， i 從 1 到 m （ m 為 s1 的長度）
   填表順序： 根據「狀態轉移」，我們需要「從上往下」填每?行，每一行「從左往右」。
   返回值： 根據「狀態表示」，我們需要返回 dp[m][n] 的值。

4. 代碼示例：

public boolean isInterleave(String s1, String s2, String s3) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = s1.length(), n = s2.length();if (m + n != s3.length()) return false; // 處理下邊界條件s1 = " " + s1;s2 = " " + s2;s3 = " " + s3;boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true; // 初始化for (int j = 1; j <= n; j++) // 初始化第??if (s2.charAt(j) == s3.charAt(j)) dp[0][j] = true;else break;for (int i = 1; i <= m; i++) // 初始化第?列if (s1.charAt(i) == s3.charAt(i)) dp[i][0] = true;else break;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j])|| (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);return dp[m][n];}

六、兩個字符串的最小ASCII刪除和

1. 題目鏈接：兩個字符串的最小ASCII刪除和
2. 題目描述：

給定兩個字符串s1 和 s2，返回 使兩個字符串相等所需刪除字符的 ASCII 值的最小和 。
示例 1:輸?: s1 = “sea”, s2 = “eat” 輸出: 231
解釋:在 “sea” 中刪除 “s” 并將 “s” 的值(115)加?總和。 在 “eat” 中刪除 “t” 并將 116 加?總和。 結束時，兩個字符串相等，115 + 116 = 231 就是符合條件的最?和。 ?例 2:
輸?: s1 = “delete”, s2 = “leet” 輸出: 403
解釋:
在 “delete” 中刪除 “dee” 字符串變成 “let”， 將 100[d]+101[e]+101[e] 加?總和。在 “leet” 中刪除 “e” 將 101[e] 加?總和。 結束時，兩個字符串都等于 “let”，結果即為 100+101+101+101 = 403 。 如果改為將兩個字符串轉換為 “lee” 或 “eet”，我們會得到 433 或 417 的結果，比答案更大。

3. 解法（動態規劃）：
   算法思路： 正難則反：求兩個字符串的最小ASCII 刪除和，其實就是找到兩個字符串中所有的公共子序列里面， ASCII 最大和。 因此，我們的思路就是按照「最長公共子序列」的分析方式來分析。
   狀態表示：
   dp[i][j] 表示： s1 的 [0, i] 區間以及 s2 的 [0, j] 區間內的所有的子序列中，公 共?序列的 ASCII 最?和。
   狀態轉移?程： 對于 dp[i][j] 根據「最后?個位置」的元素，結合題目要求，分情況討論：
   i. 當 s1[i] == s2[j] 時：應該先在 s1 的 [0, i - 1] 區間以及 s2 的 [0, j - 1] 區間內找?個公共?序列的最?和，然后在它們后面加上?個 s1[i] 字符即可。 此時 dp[i][j] = dp[i - 1][j - 1] + s1[i] ；
   ii. 當 s1[i] != s2[j] 時：公共?序列的最大和會有三種可能：
   ? s1 的 [0, i - 1] 區間以及 s2 的 [0, j] 區間內：此時 dp[i][j] = dp[i - 1][j] ； ? s1 的 [0, i] 區間以及 s2 的 [0, j - 1] 區間內：此時 dp[i][j] = dp[i][j - 1] ； ? s1 的 [0, i - 1] 區間以及 s2 的 [0, j - 1] 區間內：此時 dp[i][j] = dp[i - 1][j - 1] 。 但是前兩種情況??包含了第三種情況，因此僅需考慮前兩種情況下的最?值即可。 綜上所述，狀態轉移方程為：
   ? 當 s1[i - 1] == s2[j - 1] 時， dp[i][j] = dp[i - 1][j - 1] + s1[i] ；
   ? 當 s1[i - 1] != s2[j - 1] 時， dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
   初始化：
   a. 「空串」是有研究意義的，因此我們將原始 dp 表的規模多加上??和?列，表?空串。
   b. 引?空串后，大大的「方便我們的初始化」。
   c. 但也要注意「下標的映射」關系，以及里面的值要保證「后續填表是正確的」。
   當 s1 為空時，沒有長度，同理 s2 也是。因此第一行和第?列里面的值初始化為 0 即可保證后續填表是正確的。
   填表順序： 「從上往下」填每一行，每?行「從左往右」。
   返回值： 根據「狀態表示」，我們不能直接返回 dp 表里面的某個值：
   i. 先找到 dp[m][n] ，也是最大公共 ASCII 和；
   ii. 統計兩個字符串的 ASCII 碼和 s u m；
   iii. 返回 sum - 2 * dp[m][n]

4. 代碼示例：

 public int minimumDeleteSum(String s1, String s2) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = s1.length(), n = s2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++) {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);if (s1.charAt(i - 1) == s2.charAt(j - 1))dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + s1.charAt(i - 1));}int sum = 0; // 統計元素和for (char ch : s1.toCharArray()) sum += ch;for (char ch : s2.toCharArray()) sum += ch;return sum - dp[m][n] - dp[m][n];}

七、最長重復子數組

1. 題目鏈接：最長重復子數組
2. 題目描述：

給兩個整數數組 nums1 和 nums2 ，返回兩個數組中公共的 、長度最長的子數組的長度 。
示例 1： 輸入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
輸出：3 解釋：長度最長的公共子數組是 [3,2,1] 。
示例 2： 輸入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
輸出：5

3. 解法（動態規劃）： 算法思路： ?數組是數組中「連續」的?段，我們習慣上「以某?個位置為結尾」來研究。由于是兩個數組， 因此我們可以嘗試：以第?個數組的 i 位置為結尾以及第?個數組的 j 位置為結尾來解決問題。
   狀態表示：
   dp[i][j] 表示「以第?個數組的 i 位置為結尾」，以及「第?個數組的 j 位置為結尾公共的、長度最長的「子數組」的長度。
   狀態轉移?程： 對于 dp[i][j] ，當 nums1[i] == nums2[j] 的時候，才有意義，此時最長重復子數組的長度應該等于 1 加上除去最后?個位置時，以 i - 1, j - 1 為結尾的最長重復子數組的長度。因此，狀態轉移方程為： dp[i][j] = 1 + dp[i - 1][j - 1]
   初始化：為了處理「越界」的情況，我們可以添加?行和一列， dp 數組的下標從 1 開始，這樣就無需初始化。 第?行表示第?個數組為空，此時沒有重復子數組，因此里面的值設置成 0 即可； 第一列也是同理。
   填表順序： 根據「狀態轉移」，我們需要「從上往下」填每?行，每?行「從左往右」。
   返回值： 根據「狀態表示」，我們需要返回 dp 表里面的「最大值」。

4. 代碼示例：

 public int findLength(int[] nums1, int[] nums2) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m = nums1.length, n = nums2.length;int[][] dp = new int[m + 1][n + 1];int ret = 0;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;ret = Math.max(ret, dp[i][j]);}return ret;}

結語

本文到這里就結束了，主要通過幾道兩個數組dp問題算法題，介紹了這種類型動態規劃的做題思路，帶大家深入了解了動態規劃中兩個數組dp問題 算法這一類型。

以上就是本文全部內容，感謝各位能夠看到最后，如有問題，歡迎各位大佬在評論區指正，希望大家可以有所收獲！創作不易，希望大家多多支持！

最后，大家再見！祝好！我們下期見！