代码随想录算法训练营第四十二天-1143最长公共子序列、1035不相交的线、53最大子序和、392判断子序列

前言
状态：1143AC（方法不是最简的）、1035AC（和上一题一样）、53AC、392AC（根据 1143）
更新

1
2
3

24-07-05 初始记录
24-07-06 1143
24-07-07 1143优化、1035、53、392

初步题解

1143 最长公共子序列

题目链接：(https://leetcode.cn/problems/longest-common-subsequence/)

确定 dp[i][j] 的含义：text1 到 i；text2 到 j 位置的最长重复数组。
递推公式：如果当前位置元素相同：dp[i][j] = dp[i - 1][j - 1] + 1; ，如果当前位置元素不同：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 。
dp 数组的初始化：针对初始元素是否相同及 i = 0 和 j = 0 的两种情况，都需要分别判断。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public static int longestCommonSubsequence(String text1, String text2) {  
    int[][] dp = new int[text1.length()][text2.length()];  
  
    int maxLength = 0;  
  
    for (int i = 0; i < text1.length(); i++) {  
        for (int j = 0; j < text2.length(); j++) {  
            // 当前指针位置相同，dp[i][j] = dp[i - 1][j - 1] + 1  
            if (text1.charAt(i) == text2.charAt(j)) {  
                if (i == 0 || j == 0) {  
                    dp[i][j] = 1;  
                    maxLength = Math.max(dp[i][j], maxLength);  
                    continue;  
                }  
                dp[i][j] = dp[i - 1][j - 1] + 1;  
            } else {  
                if (i == 0 && j == 0) {  
                    dp[i][j] = 0;  
                    continue;  
                } else if (i == 0) {  
                    dp[i][j] = dp[0][j - 1];  
                    maxLength = Math.max(dp[i][j], maxLength);  
                    continue;  
                } else if (j == 0) {  
                    dp[i][j] = dp[i - 1][0];  
                    maxLength = Math.max(dp[i][j], maxLength);  
                    continue;  
                }  
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  
            }  
            maxLength = Math.max(dp[i][j], maxLength);  
        }  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
  
    return maxLength;  
}

1035 不相交的线

题目链接：(https://leetcode.cn/problems/uncrossed-lines)

确定 dp[i][j] 的含义：text1 到 i - 1；text2 到 j - 1 位置的最长重复数组。
递推公式：如果当前位置元素相同：dp[i][j] = dp[i - 1][j - 1] + 1; ，如果当前位置元素不同：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 。
dp 数组的初始化：i = 0 或 j = 0 时，dp 值为 0
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public int maxUncrossedLines(int[] nums1, int[] nums2) {  
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];  
  
    for (int i = 1; i <= nums1.length; i++) {  
        for (int j = 1; j <= nums2.length; 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]);  
            }  
        }  
    }  
  
    // System.out.println(Arrays.deepToString(dp));  
  
    return dp[nums1.length][nums2.length];  
}

53 最大子序和

题目链接：(https://leetcode.cn/problems/maximum-subarray/)

确定 dp[i] 的含义：数组长度为 i 时的最大子序和。
递推公式：如果当前位置元素相同：dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); 。
dp 数组的初始化：i = 0 时，取 nums[0] 的值
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public int maxSubArray(int[] nums) {  
    int[] dp = new int[nums.length];  
  
    dp[0] = nums[0];  
    int max = dp[0];  
  
    for (int i = 1; i < dp.length; i++) {  
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);  
        max = Math.max(max, dp[i]);  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return max;  
}

392 判断子序列

确定 dp[i][j] 的含义：s 到 i - 1；t 到 j - 1 位置的相同子序列长度。
递推公式：如果当前位置元素相同：dp[i][j] = dp[i - 1][j - 1] + 1; ，如果当前位置元素不同：dp[i][j] = dp[i][j - 1]; 。
dp 数组的初始化：i = 0 或 j = 0 时，dp 值为 0
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

题目链接：(https://leetcode.cn/problems/is-subsequence)

public boolean isSubsequence(String s, String t) {  
    int[][] dp = new int[s.length() + 1][t.length() + 1];  
    
    for (int i = 1; i <= s.length(); i++) {  
        for (int j = 1; j <= t.length(); j++) {  
            // 当前指针位置相同，dp[i][j] = dp[i - 1][j - 1] + 1  
            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];  
            }  
        }  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
  
    return dp[s.length()][t.length()] == s.length();  
}

看解析

1143 最长公共子序列

解析：(https://programmercarl.com/1143.最长公共子序列.html)

二维数组优化
1. dp 数组的定义修改为 dp[i][j]：长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列为 dp[i][j]（即多）
2. 初始化即 i 为 0，j 为 0 时，dp[i][j] 的值也为 0

public int longestCommonSubsequence(String text1, String text2) {  
    int[][] dp = new int[text1.length() + 1][text2.length() + 1];  

    for (int i = 1; i <= text1.length(); i++) {  
        for (int j = 1; j <= text2.length(); j++) {  
            // 当前指针位置相同，dp[i][j] = dp[i - 1][j - 1] + 1  
            if (text1.charAt(i - 1) == text2.charAt(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]);  
            }  
        }  
    }  
  
	// System.out.println(Arrays.deepToString(dp));  
  
    return dp[text1.length()][text2.length()];  
}

一维数组优化

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