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 的长度。

总结

在处理动态规划问题时，选择合适的数据类型至关重要，它直接影响到算法的正确性和效率。对于子序列问题，使用整数类型的动态规划数组能够更准确地表示状态和完成状态转移，从而得到正确的结果。