---

day53学习内容

day53主要内容

• 最长公共子序列
• 不相交的线
• 最大子序和

---

声明
本文思路和文字，引用自《代码随想录》

---

一、最长公共子序列

1143.原题链接

1.1、动态规划五部曲

1.1.1、 确定dp数组（dp table）以及下标的含义

• dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度。

1.1.2、确定递推公式

基本思路
我们可以根据两个字符串中当前字符是否相等，采取不同的策略来更新 dp 表。
与最长公共子数组（或子串）不同，子序列不要求元素在原字符串中是连续的，只要求它们保持相对顺序即可。

推导状态转移方程

1. 字符匹配的情况：
   当 text1[i-1] == text2[j-1] 时，这意味着这两个字符可以成为目前为止考虑的字符串的公共子序列的一部分。因此，这两个字符将增加公共子序列的长度，即

dp[i][j]=dp[i−1][j−1]+1

这个方程表明，text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列可以通过在它们的前 i-1 个字符和前 j-1 个字符的最长公共子序列的基础上添加这两个匹配的字符来得到。

2. 字符不匹配的情况：
   当 text1[i-1] != text2[j-1] 时，最长公共子序列不能同时包括这两个字符。因此，有以下两种可能性：
   • 忽略 text1 的当前字符 i-1，只考虑 text1 的前 i-1 个字符和 text2 的前 j 个字符。
   • 忽略 text2 的当前字符 j-1，只考虑 text1 的前 i 个字符和 text2 的前 j-1 个字符。
     这两种情况下的最长公共子序列的长度将是：

dp[i][j]=max(dp[i−1][j],dp[i][j−1])

这个方程表明，当前的 dp[i][j] 应取前面两种情况中更长的子序列长度。

1.1.3、 dp数组如何初始化

• dp[0][x] 和 dp[x][0] 应该初始化为 0，因为一个长度为 0 的字符串与任何字符串的最长公共子序列长度都是 0。
• 或者这句话看不懂，就画个图。。。看一下推导的方向就明白了
  
  图引用自卡尔的视频。

https://www.bilibili.com/video/BV1ye4y1L7CQ/?spm_id_from=pageDriver&vd_source=266f115062b99cd2d8e5185add0b8cc9

1.1.4、确定遍历顺序

从小到大遍历

1.1.5、输出结果

• return dp[text1.length()][text2.length()]; 最后，dp 数组的最后一个元素（即 dp[text1.length()][text2.length()]）包含了整个 text1 和 text2 的最长公共子序列的长度。

1.2、代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 创建二维数组dp，大小为text1长度+1和text2长度+1
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        // 遍历text1的每一个字符
        for (int i = 1; i <= text1.length(); i++) {
            char char1 = text1.charAt(i - 1); // 获取text1的第i-1个字符
            // 遍历text2的每一个字符
            for (int j = 1; j <= text2.length(); j++) {
                char char2 = text2.charAt(j - 1); // 获取text2的第j-1个字符

                // 如果两个字符相同
                if (char1 == char2) {
                    // 如果当前的两个字符相同，则当前dp[i][j]应基于之前的dp[i-1][j-1]的值加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果两个字符不同，选择之前两种情况的较大者作为当前dp[i][j]的值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 返回数组的最后一个元素，即为text1和text2的最长公共子序列长度
        return dp[text1.length()][text2.length()];
    }
}

二、不相交的线

1035.原题链接

它实质上和最长公共子序列（LCS）问题相同，只是在不同的上下文中应用。在这个问题中，我们要在两个数组中找到最多的对应数字（或线），使得这些数字的顺序在两个数组中保持一致，但不必连续。

2.1、动态规划五部曲

2.1.1、 确定dp数组（dp table）以及下标的含义

• 其中 dp[i][j] 代表考虑 nums1 的前 i 个元素和 nums2 的前 j 个元素时的最大不相交线数（或最长公共子序列的长度）。

2.1.2、确定递推公式

• for (int i = 1; i <= len1; i++)：外层循环遍历 nums1。
• for (int j = 1; j <= len2; j++)：内层循环遍历 nums2。
  • if (nums1[i - 1] == nums2[j - 1])：如果当前考虑的两个元素相等，表示可以在此基础上形成一个新的对应线，所以 dp[i][j] = dp[i - 1][j - 1] + 1;。这意味着我们在之前的最大对应线数的基础上增加一条新的线。
  • else：如果当前的两个元素不相等，则我们需要决定是跳过 nums1 的当前元素还是 nums2 的当前元素，以保持最大的对应线数。因此，dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 选择这两种情况中较大的一个。

2.1.3、 dp数组如何初始化

根据前面的分析。dp 表的最后一个元素就是两个数组中可以形成的最大不相交线数，这等同于最长公共子序列的长度。所以初始化逻辑和上面那题是一样的，这里不再赘述了。

2.1.4、确定遍历顺序

从小到大遍历

2.1.5、输出结果

• return dp[len1][len2]; 动态规划表的最后一个元素包含了整个 nums1 和 nums2 可以形成的最大不相交线数。

2.2、代码

class Solution {
    // maxUncrossedLines 方法用来计算两个数组间的最大未交叉线数
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // len1 和 len2 分别是两个数组的长度
        int len1 = nums1.length;
        int len2 = nums2.length;
        // dp 数组用于存储动态规划的中间结果
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 外层循环遍历 nums1
        for (int i = 1; i <= len1; i++) {
            // 内层循环遍历 nums2
            for (int j = 1; j <= len2; j++) {
                // 如果当前两个数组的元素相等，更新 dp 数组的值
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果不相等，取两种情况的较大值，即不包含当前 nums1 的元素或不包含当前 nums2 的元素
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 返回 dp 数组右下角的值，即为最大未交叉线数
        return dp[len1][len2];
    }
}

三、最大子序和

53.原题链接

3.1、动态规划五部曲

3.1.1、 确定dp数组（dp table）以及下标的含义

• dp[i] 表示以第 i 个元素结尾的最大子数组和。

3.1.2、确定递推公式

• 从数组的第二个元素开始遍历（即i=1）。
• 对于每个元素nums[i]，更新dp[i]。这里的转移方程是：
  • dp[i] = Math.max(dp[i-1] + nums[i], nums[i])；
  • 这个方程的意思是，考虑到第i个元素时，最大子数组和可以是：
    • dp[i-1] + nums[i]（即包含之前的最大子数组和再加上当前元素nums[i]），或者
    • nums[i]本身（即从新开始计数，只取当前元素，这种情况适用于dp[i-1]是负数，不如放弃之前的累计，重新开始）。
• 同时更新结果res，如果dp[i]比当前的res还要大，就用dp[i]更新res。

3.1.3、 dp数组如何初始化

dp[0]即为nums[0]，因为第一个元素前面没有其他元素，所以它自身就是一个子数组。

3.1.4、确定遍历顺序

从小到大遍历

3.1.5、输出结果

最后返回 res，它存储的是整个数组的最大子数组和。

3.2、代码

class Solution {
    public int maxSubArray(int[] nums) {
        // 如果数组为空，则直接返回0（通常情况下，这里可以根据题意返回负无穷或抛出异常）
        if (nums.length == 0) {
            return 0;
        }

        // res用来存储最终的最大子数组和，初值设为数组的第一个元素
        int res = nums[0];
        // dp数组用于动态规划存储到当前元素为止的最大子数组和，dp[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 = Math.max(res, dp[i]);
        }
        // 返回计算得到的最大子数组和
        return res;
    }
}

总结

1.感想

• 补周六的进度，冲

2.思维导图

本文思路引用自代码随想录，感谢代码随想录作者。