1143. 最長公共子序列

給定兩個字符串 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 。

方法一：

/*二維dp數組
*/
class Solution {public int longestCommonSubsequence(String text1, String text2) {// char[] char1 = text1.toCharArray();// char[] char2 = text2.toCharArray();// 可以在一開始的時候就先把text1, text2 轉成char[]，之後就不需要有這麼多爲了處理字串的調整// 就可以和卡哥的code更一致int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先對dp數組做初始化操作for (int i = 1 ; i <= text1.length() ; i++) {char char1 = text1.charAt(i - 1);for (int j = 1; j <= text2.length(); j++) {char char2 = text2.charAt(j - 1);if (char1 == char2) { // 開始列出狀態轉移方程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[text1.length()][text2.length()];}
}

這段代碼是用于解決「兩個字符串的最長公共子序列」問題的Java實現。給定兩個字符串 text1 和 text2，目標是找到在這兩個字符串中都出現的最長公共子序列的長度。子序列是指從原序列中刪除一些或不刪除元素且保持剩余元素的相對順序不變形成的序列。

代碼解析

1. 初始化動態規劃數組:

   • 創建一個二維數組 dp，其大小為 (text1.length() + 1) x (text2.length() + 1)。dp[i][j] 的值代表 text1 的前 i 個字符和 text2 的前 j 個字符的最長公共子序列的長度。額外的一列和一行是為了方便邊界條件的處理，其中 dp[0][j] 和 dp[i][0] 的值默認為0，因為沒有任何字符時，最長公共子序列的長度為0。

2. 動態規劃迭代:

   • 從1到 text1.length() 遍歷 text1 的每個字符，從1到 text2.length() 遍歷 text2 的每個字符。
   • 對于 text1 的第 i 個字符 char1 和 text2 的第 j 個字符 char2：
     • 如果 char1 等于 char2，那么 text1 的前 i 個字符和 text2 的前 j 個字符的最長公共子序列的長度等于 text1 的前 i-1 個字符和 text2 的前 j-1 個字符的最長公共子序列的長度加1，即 dp[i-1][j-1] + 1。
     • 如果 char1 不等于 char2，那么最長公共子序列的長度等于 text1 的前 i 個字符和 text2 的前 j-1 個字符的最長公共子序列的長度與 text1 的前 i-1 個字符和 text2 的前 j 個字符的最長公共子序列的長度中的較大值，即 Math.max(dp[i-1][j], dp[i][j-1])。

3. 返回結果:

   • 最后返回 dp[text1.length()][text2.length()]，即 text1 和 text2 的最長公共子序列的長度。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是字符串 text1 和 text2 的長度。這是因為需要遍歷兩個字符串的所有可能的字符組合來計算最長公共子序列的長度。
• 空間復雜度: O(m * n)，需要一個大小為 (m + 1) x (n + 1) 的動態規劃數組 dp 來存儲中間結果。

總結

這段代碼通過動態規劃的方法，有效地解決了兩個字符串的最長公共子序列問題。盡管時間復雜度和空間復雜度較高，但在許多實際應用場景中，這樣的性能通常是可接受的，特別是當字符串長度適中時。如果需要進一步優化空間復雜度，可以考慮使用滾動數組技術，將空間復雜度降低到 O(min(m, n))。

方法二：

/**一維dp數組
*/
class Solution {public int longestCommonSubsequence(String text1, String text2) {int n1 = text1.length();int n2 = text2.length();// 多從二維dp數組過程分析  // 關鍵在于  如果記錄  dp[i - 1][j - 1]// 因為 dp[i - 1][j - 1]  <!=>  dp[j - 1]  <=>  dp[i][j - 1]int [] dp = new int[n2 + 1];for(int i = 1; i <= n1; i++){// 這里pre相當于 dp[i - 1][j - 1]int pre = dp[0];for(int j = 1; j <= n2; j++){//用于給pre賦值int cur = dp[j];if(text1.charAt(i - 1) == text2.charAt(j - 1)){//這里pre相當于dp[i - 1][j - 1]   千萬不能用dp[j - 1] !!dp[j] = pre + 1;} else{// dp[j]     相當于   dp[i - 1][j]// dp[j - 1] 相當于   dp[i][j - 1]dp[j] = Math.max(dp[j], dp[j - 1]);}//更新dp[i - 1][j - 1], 為下次使用做準備pre = cur;}}return dp[n2];}
}

這段代碼是用于解決「兩個字符串的最長公共子序列」問題的Java實現，特別之處在于它使用了滾動數組（一維dp數組）技術來優化空間復雜度。給定兩個字符串 text1 和 text2，目標是找到在這兩個字符串中都出現的最長公共子序列的長度。

代碼解析

1. 初始化動態規劃數組:

   • 創建一個一維數組 dp，其大小為 text2.length() + 1。dp[j] 的值代表 text1 的前 i 個字符和 text2 的前 j 個字符的最長公共子序列的長度，其中 i 是外層循環的索引。額外的一列是為了方便邊界條件的處理。

2. 動態規劃迭代:

   • 外層循環從1到 text1.length() 遍歷 text1 的每個字符。
   • 內層循環從1到 text2.length() 遍歷 text2 的每個字符。
   • 使用一個變量 pre 來輔助存儲 dp[j - 1] 的值，以便在更新 dp[j] 時能夠訪問到 dp[i-1][j-1] 的值。
   • 對于 text1 的第 i 個字符和 text2 的第 j 個字符：
     • 如果兩個字符相等，那么最長公共子序列的長度等于前一個狀態的最長公共子序列長度加1，即 pre + 1。
     • 如果兩個字符不相等，那么最長公共子序列的長度等于 dp[j] 和 dp[j - 1] 中的較大值。

3. 更新與記錄:

   • 在內層循環中，每次更新 dp[j] 后，立即使用 cur 來保存舊的 dp[j] 的值，然后更新 pre 為 cur，為下一輪迭代做準備。

4. 返回結果:

   • 最后返回 dp[n2]，即 text1 和 text2 的最長公共子序列的長度。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是字符串 text1 和 text2 的長度。這是因為需要遍歷兩個字符串的所有可能的字符組合來計算最長公共子序列的長度。
• 空間復雜度: O(n)，其中 n 是 text2 的長度。使用了一維數組 dp 來存儲中間結果，相比于二維數組，空間復雜度顯著降低。

總結

這段代碼通過滾動數組的動態規劃方法，有效地解決了兩個字符串的最長公共子序列問題，同時在空間復雜度方面進行了優化。滾動數組技術避免了使用額外的大量空間，使得算法在處理大規模數據時更加高效。通過引入輔助變量 pre 來保存前一個狀態的信息，確保了狀態轉移方程的正確性，即使在使用一維數組的情況下也能正確地執行動態規劃。

1035. 不相交的線

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

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

nums1[i] == nums2[j]
且繪制的直線不與任何其他連線（非水平線）相交。
請注意，連線即使在端點也不能相交：每個數字只能屬于一條連線。

以這種方法繪制線條，并返回可以繪制的最大連線數。
輸入：nums1 = [1,4,2], nums2 = [1,2,4]
輸出：2
解釋：可以畫出兩條不交叉的線，如上圖所示。
但無法畫出第三條不相交的直線，因為從 nums1[1]=4 到 nums2[2]=4 的直線將與從 nums1[2]=2 到 nums2[1]=2 的直線相交。

  class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; 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[len1][len2];}
}

這段代碼是用于解決「最大不相交線段對」問題的Java實現，其實質上是求解兩個整數數組 nums1 和 nums2 的最長公共子序列（Longest Common Subsequence, LCS）問題的一種應用。給定兩個整數數組，目標是找到兩數組中元素對的個數，使得這些元素對可以形成不相交的線段對，其中每個線段對連接 nums1 和 nums2 中相同的元素。

代碼解析

1. 初始化動態規劃數組:

   • 創建一個二維數組 dp，其大小為 (len1 + 1) x (len2 + 1)。dp[i][j] 的值代表 nums1 的前 i 個元素和 nums2 的前 j 個元素可以形成的最大不相交線段對的數量。額外的一列和一行是為了方便邊界條件的處理，其中 dp[0][j] 和 dp[i][0] 的值默認為0，因為沒有元素時，最大不相交線段對的數量為0。

2. 動態規劃迭代:

   • 從1到 len1 遍歷 nums1 的每個元素，從1到 len2 遍歷 nums2 的每個元素。
   • 對于 nums1 的第 i 個元素和 nums2 的第 j 個元素：
     • 如果兩個元素相等，那么 nums1 的前 i 個元素和 nums2 的前 j 個元素可以形成的最大不相交線段對的數量等于 nums1 的前 i-1 個元素和 nums2 的前 j-1 個元素可以形成的最大不相交線段對的數量加1，即 dp[i-1][j-1] + 1。
     • 如果兩個元素不相等，那么最大不相交線段對的數量等于 nums1 的前 i-1 個元素和 nums2 的前 j 個元素可以形成的最大不相交線段對的數量與 nums1 的前 i 個元素和 nums2 的前 j-1 個元素可以形成的最大不相交線段對的數量中的較大值，即 Math.max(dp[i-1][j], dp[i][j-1])。

3. 返回結果:

   • 最后返回 dp[len1][len2]，即 nums1 和 nums2 可以形成的最大不相交線段對的數量。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是數組 nums1 和 nums2 的長度。這是因為需要遍歷兩個數組的所有可能的元素組合來計算最大不相交線段對的數量。
• 空間復雜度: O(m * n)，需要一個大小為 (m + 1) x (n + 1) 的動態規劃數組 dp 來存儲中間結果。

總結

這段代碼通過動態規劃的方法，有效地解決了最大不相交線段對問題。雖然時間復雜度和空間復雜度較高，但在許多實際應用場景中，這樣的性能通常是可接受的，特別是當數組大小適中時。如果需要進一步優化空間復雜度，可以考慮使用滾動數組技術，將空間復雜度降低到 O(min(m, n))。

53. 最大子數組和

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

子數組
是數組中的一個連續部分。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。
示例 2：

輸入：nums = [1]
輸出：1
示例 3：

輸入：nums = [5,4,-1,7,8]
輸出：23

方法一：

   /*** 1.dp[i]代表當前下標對應的最大值* 2.遞推公式 dp[i] = max (dp[i-1]+nums[i],nums[i]) res = max(res,dp[i])* 3.初始化 都為 0* 4.遍歷方向，從前往后* 5.舉例推導結果。。。** @param nums* @return*/public static int maxSubArray(int[] nums) {if (nums.length == 0) {return 0;}int res = nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);res = res > dp[i] ? res : dp[i];}return res;}

這段代碼是用于解決「最大子數組和」問題的Java實現，實質上是在一個整數數組中找到具有最大和的連續子數組的和。給定一個整數數組 nums，目標是找到其中連續子數組的最大和。

代碼解析

1. 初始化動態規劃數組和結果變量:

   • 創建一個與 nums 長度相等的數組 dp，其中 dp[i] 代表以 nums[i] 結尾的連續子數組的最大和。
   • 初始化 dp[0] 為 nums[0]，因為數組的第一個元素自身就可以構成一個連續子數組。
   • 初始化結果變量 res 為 nums[0]，用于跟蹤整個數組中連續子數組的最大和。

2. 動態規劃迭代:

   • 從數組的第二個元素開始迭代，對于每一個元素 nums[i]（從索引1開始到 nums.length - 1）。
   • 計算以 nums[i] 結尾的連續子數組的最大和，這可以通過比較 dp[i-1] + nums[i] 和 nums[i] 得到，即選擇將當前元素添加到前一個連續子數組的末尾，或者將當前元素作為一個新的連續子數組的開始。
   • 更新 dp[i] 為這個比較的結果。

3. 記錄結果:

   • 在每次更新 dp[i] 后，同時更新全局最大值 res，以確保在整個迭代過程中始終保存連續子數組的最大和。

4. 返回結果:

   • 最后返回 res，即整個數組中的連續子數組的最大和。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 nums 的長度。這是因為只需要遍歷數組一次來計算連續子數組的最大和。
• 空間復雜度: O(n)，需要一個長度為 n 的動態規劃數組 dp 來存儲中間結果。

總結

這段代碼通過動態規劃的方法，有效地解決了最大子數組和問題。盡管時間復雜度為 O(n)，但在空間復雜度方面，實際上我們可以進一步優化，使用常數級別的空間復雜度。這是因為狀態轉移方程只依賴于前一個狀態，我們并不需要保存整個 dp 數組。在實際應用中，可以僅使用幾個變量來代替整個數組，將空間復雜度降低到 O(1)。以下是簡化后的代碼示例：

public static int maxSubArray(int[] nums) {if (nums.length == 0) {return 0;}int res = nums[0];int prevMax = nums[0];for (int i = 1; i < nums.length; i++) {prevMax = Math.max(prevMax + nums[i], nums[i]);res = Math.max(res, prevMax);}return res;
}

在這個簡化版本中，我們不再使用 dp 數組，而是使用變量 prevMax 來存儲前一個元素的最大連續子數組和，從而實現了空間復雜度的優化。

方法二：

//因為dp[i]的遞推公式只與前一個值有關，所以可以用一個變量代替dp數組，空間復雜度為O(1)
class Solution {public int maxSubArray(int[] nums) {int res = nums[0];int pre = nums[0];for(int i = 1; i < nums.length; i++) {pre = Math.max(pre + nums[i], nums[i]);res = Math.max(res, pre);}return res;}
}

這段代碼是用于解決「最大子數組和」問題的Java實現，采用了一種空間優化的動態規劃方法。給定一個整數數組 nums，目標是找到其中連續子數組的最大和。

代碼解析

1. 初始化變量:

   • 初始化結果變量 res 為 nums[0]，用于跟蹤整個數組中連續子數組的最大和。
   • 初始化變量 pre 為 nums[0]，用于存儲前一個元素的最大連續子數組和，這個變量在后續迭代中會不斷更新。

2. 動態規劃迭代:

   • 從數組的第二個元素開始迭代，對于每一個元素 nums[i]（從索引1開始到 nums.length - 1）。
   • 更新 pre 的值，使其成為 pre + nums[i] 和 nums[i] 中較大的那個值。這里的邏輯是：如果前一個連續子數組的和加上當前元素比當前元素自身的值大，則選擇前者；否則，選擇當前元素作為新的連續子數組的起始點。
   • 每次更新完 pre 的值之后，更新 res 的值，確保 res 始終保存的是從開始到當前元素為止所遇到的最大連續子數組和。

3. 返回結果:

   • 最后返回 res，即整個數組中的連續子數組的最大和。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 nums 的長度。這是因為只需要遍歷數組一次來計算連續子數組的最大和。
• 空間復雜度: O(1)，因為只使用了固定數量的變量，而沒有使用額外的數據結構，如數組或列表。

總結

這段代碼通過動態規劃的方法，有效地解決了最大子數組和問題，并通過使用單一變量 pre 替代動態規劃數組，將空間復雜度從 O(n) 優化到了 O(1)。這種方法不僅保持了算法的高效性，同時也降低了空間占用，尤其適用于處理大數據量的場景。在實際應用中，這種空間優化的動態規劃方法非常實用，可以提高程序的運行效率和資源利用率。

392. 判斷子序列

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

進階：

如果有大量輸入的 S，稱作 S1, S2, … , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？

致謝：

特別感謝 @pbrother 添加此問題并且創建所有測試用例。

示例 1：

輸入：s = “abc”, t = “ahbgdc”
輸出：true
示例 2：

輸入：s = “axc”, t = “ahbgdc”
輸出：false

方法一：

在這里插入代碼片class Solution {public boolean isSubsequence(String s, String t) {int length1 = s.length(); int length2 = t.length();int[][] dp = new int[length1+1][length2+1];for(int i = 1; i <= length1; i++){for(int j = 1; j <= length2; j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = dp[i][j-1];}}}if(dp[length1][length2] == length1){return true;}else{return false;}}
}

這段代碼是用于判斷一個字符串 s 是否是另一個字符串 t 的子序列的Java實現，通過使用動態規劃的方法來解決這個問題。子序列是指從原序列中刪除一些或不刪除元素且保持剩余元素的相對順序不變形成的序列。

代碼解析

1. 初始化動態規劃數組:

   • 創建一個二維數組 dp，其大小為 (length1 + 1) x (length2 + 1)。dp[i][j] 的值代表 s 的前 i 個字符和 t 的前 j 個字符組成的子序列的最大匹配長度。額外的一列和一行是為了方便邊界條件的處理，其中 dp[0][j] 和 dp[i][0] 的值默認為0，因為沒有任何字符時，最長匹配長度為0。

2. 動態規劃迭代:

   • 從1到 length1 遍歷 s 的每個字符，從1到 length2 遍歷 t 的每個字符。
   • 對于 s 的第 i 個字符和 t 的第 j 個字符：
     • 如果兩個字符相等，那么 s 的前 i 個字符和 t 的前 j 個字符組成的子序列的最大匹配長度等于 s 的前 i-1 個字符和 t 的前 j-1 個字符組成的子序列的最大匹配長度加1，即 dp[i-1][j-1] + 1。
     • 如果兩個字符不相等，那么最大匹配長度等于 s 的前 i 個字符和 t 的前 j-1 個字符組成的子序列的最大匹配長度，即 dp[i][j-1]。

3. 判斷結果:

   • 最后檢查 dp[length1][length2] 的值是否等于 length1，如果等于，說明 s 是 t 的子序列，返回 true；否則，返回 false。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是字符串 s 和 t 的長度。這是因為需要遍歷兩個字符串的所有可能的字符組合來計算子序列的最大匹配長度。
• 空間復雜度: O(m * n)，需要一個大小為 (m + 1) x (n + 1) 的動態規劃數組 dp 來存儲中間結果。

總結

這段代碼通過動態規劃的方法，有效地解決了字符串子序列判斷問題。盡管時間復雜度和空間復雜度較高，但在許多實際應用場景中，這樣的性能通常是可接受的，特別是當字符串長度適中時。如果需要進一步優化空間復雜度，可以考慮使用滾動數組技術，將空間復雜度降低到 O(min(m, n))。然而，對于此特定問題，還有更簡單的解決方案，例如使用雙指針法，可以達到 O(n) 的時間復雜度和 O(1) 的空間復雜度。

方法二：

class Solution {public boolean isSubsequence(String s, String t) {// 修改遍歷順序，外圈遍歷t，內圈遍歷s。使得dp的推算只依賴正上方和左上方，方便壓縮。int[][] dp = new int[t.length() + 1][s.length() + 1];for (int i = 1; i < dp.length; i++) { // 遍歷t字符串for (int j = 1; j < dp[i].length; j++) { // 遍歷s字符串if (t.charAt(i - 1) == s.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = dp[i - 1][j];}}System.out.println(Arrays.toString(dp[i]));}return dp[t.length()][s.length()] == s.length();}
}

這段代碼同樣是用于判斷一個字符串 s 是否是另一個字符串 t 的子序列的Java實現，但是它通過調整遍歷順序和動態規劃數組的使用方式，來優化動態規劃的過程，使其更容易進行空間上的優化，比如使用滾動數組技術。

代碼解析

1. 初始化動態規劃數組:

   • 創建一個二維數組 dp，其大小為 (t.length() + 1) x (s.length() + 1)。dp[i][j] 的值代表 t 的前 i 個字符和 s 的前 j 個字符組成的子序列的最大匹配長度。額外的一列和一行是為了方便邊界條件的處理，其中 dp[0][j] 和 dp[i][0] 的值默認為0，因為沒有任何字符時，最長匹配長度為0。

2. 動態規劃迭代:

   • 外層循環從1到 t.length() 遍歷 t 的每個字符，內層循環從1到 s.length() 遍歷 s 的每個字符。
   • 對于 t 的第 i 個字符和 s 的第 j 個字符：
     • 如果兩個字符相等，那么 t 的前 i 個字符和 s 的前 j 個字符組成的子序列的最大匹配長度等于 t 的前 i-1 個字符和 s 的前 j-1 個字符組成的子序列的最大匹配長度加1，即 dp[i-1][j-1] + 1。
     • 如果兩個字符不相等，那么最大匹配長度等于 t 的前 i-1 個字符和 s 的前 j 個字符組成的子序列的最大匹配長度，即 dp[i-1][j]。

3. 判斷結果:

   • 最后檢查 dp[t.length()][s.length()] 的值是否等于 s.length()，如果等于，說明 s 是 t 的子序列，返回 true；否則，返回 false。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是字符串 t 和 s 的長度。這是因為需要遍歷兩個字符串的所有可能的字符組合來計算子序列的最大匹配長度。
• 空間復雜度: O(m * n)，需要一個大小為 (m + 1) x (n + 1) 的動態規劃數組 dp 來存儲中間結果。

空間優化

由于狀態轉移方程只依賴于前一行和前一列的狀態，可以進一步優化空間復雜度到 O(min(m, n))，使用滾動數組技術，如下所示：

class Solution {public boolean isSubsequence(String s, String t) {int[] dp = new int[s.length() + 1];for (int i = 1; i <= t.length(); i++) {for (int j = dp.length - 1; j > 0; j--) {if (t.charAt(i - 1) == s.charAt(j - 1)) {dp[j] = dp[j - 1] + 1;} else {dp[j] = dp[j];}}}return dp[s.length()] == s.length();}
}

在上面的優化版本中，我們使用了一個一維數組 dp 來代替原來的二維數組，通過從后往前更新數組，確保了每個狀態的更新不會影響到它所依賴的前一個狀態。

方法三：

class Solution {public boolean isSubsequence(String s, String t) {int[] dp = new int[s.length() + 1];for (int i = 0; i < t.length(); i ++) {// 需要使用上一輪的dp[j - 1]，所以使用倒序遍歷for (int j = dp.length - 1; j > 0; j --) {// i遍歷的是t字符串，j遍歷的是dp數組，dp數組的長度比s的大1，因此需要減1。if (t.charAt(i) == s.charAt(j - 1)) {dp[j] = dp[j - 1] + 1;}}}return dp[s.length()] == s.length();}
}

這段代碼是用于判斷一個字符串 s 是否是另一個字符串 t 的子序列的Java實現，采用了滾動數組的空間優化技術，將動態規劃的空間復雜度從 O(m * n) 優化到了 O(n)，其中 n 是字符串 s 的長度。

代碼解析

1. 初始化動態規劃數組:

   • 創建一個一維數組 dp，其大小為 (s.length() + 1)。dp[j] 的值代表 t 的前 i 個字符和 s 的前 j-1 個字符組成的子序列的最大匹配長度。額外的一列是為了方便邊界條件的處理，其中 dp[0] 的值默認為0，因為沒有任何字符時，最長匹配長度為0。

2. 動態規劃迭代:

   • 外層循環從0到 t.length() 遍歷 t 的每個字符，內層循環從 dp.length - 1 到 1 反向遍歷 dp 數組。
   • 對于 t 的第 i 個字符和 dp 數組的第 j 個元素：
     • 如果 t 的第 i 個字符等于 s 的第 j-1 個字符，那么 dp[j] 的值更新為 dp[j - 1] + 1。
     • 如果兩個字符不相等，dp[j] 的值保持不變，即 dp[j]。

3. 判斷結果:

   • 最后檢查 dp[s.length()] 的值是否等于 s.length()，如果等于，說明 s 是 t 的子序列，返回 true；否則，返回 false。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是字符串 t 和 s 的長度。這是因為需要遍歷兩個字符串的所有可能的字符組合來計算子序列的最大匹配長度。
• 空間復雜度: O(n)，需要一個大小為 (s.length() + 1) 的一維動態規劃數組 dp 來存儲中間結果。

關于倒序遍歷

使用倒序遍歷 dp 數組的主要原因是狀態轉移方程的依賴關系。由于 dp[j] 的更新依賴于 dp[j - 1] 的值，為了避免在更新 dp[j] 的過程中覆蓋掉尚未使用的 dp[j - 1] 的值，需要先保存 dp[j - 1] 的舊值，然后再進行更新。通過倒序遍歷，可以確保在更新 dp[j] 時，dp[j - 1] 的值仍然是上一輪的值，從而正確地完成了狀態轉移。

總結

通過使用滾動數組和倒序遍歷的技術，這段代碼有效地解決了字符串子序列判斷的問題，同時在空間復雜度方面進行了優化，使其更加適合處理大規模數據的情況。這種空間優化的動態規劃方法在實際編程中非常常見，尤其是在需要平衡時間和空間資源的應用場景中。

方法四：

class Solution { public boolean isSubsequence(String s, String t) {boolean[] dp = new boolean[s.length() + 1];// 表示 “” 是t的子序列dp[0] = true;for (int i = 0; i < t.length(); i ++) {for (int j = dp.length - 1; j > 0; j --) {if (t.charAt(i) == s.charAt(j - 1)) {dp[j] = dp[j - 1];}}}return dp[dp.length - 1];}
}

這段代碼是用于判斷一個字符串 s 是否是另一個字符串 t 的子序列的Java實現，但它存在一個邏輯錯誤，即將動態規劃數組 dp 定義為布爾類型數組，這并不適合用來解決此類問題。通常情況下，動態規劃數組應包含具體的數值，用以表示某種狀態的量化值，而不是布爾值。

代碼解析（修正版）

為了糾正上述代碼的邏輯錯誤，我們可以將其修改為使用整數類型的動態規劃數組，類似于之前的討論中所展示的。以下是修正后的代碼：

class Solution {public boolean isSubsequence(String s, String t) {int[] dp = new int[s.length() + 1];dp[0] = 0; // 空字符串總是任意字符串的子序列for (int i = 0; i < t.length(); i++) {for (int j = dp.length - 1; j > 0; j--) {if (t.charAt(i) == s.charAt(j - 1)) {dp[j] = dp[j - 1] + 1;}}}return dp[s.length()] == s.length();}
}

修正說明

• 動態規劃數組類型：將 boolean[] dp 更改為 int[] dp。
• 初始化：將 dp[0] 設置為 true 更改為 dp[0] = 0。這是因為 dp[j] 的值應該表示到目前為止匹配的字符數量，而不是一個布爾標志。
• 判斷條件：最終的判斷條件也相應地更改，從 return dp[dp.length - 1]; 更改為 return dp[s.length()] == s.length();，以檢查 s 的所有字符是否都能在 t 中找到對應的子序列。

時間復雜度和空間復雜度

• 時間復雜度: O(m * n)，其中 m 和 n 分別是字符串 t 和 s 的長度。
• 空間復雜度: O(n)，其中 n 是字符串 s 的長度。

總結

在處理動態規劃問題時，選擇合適的數據類型至關重要，它直接影響到算法的正確性和效率。對于子序列問題，使用整數類型的動態規劃數組能夠更準確地表示狀態和完成狀態轉移，從而得到正確的結果。