[C国演义] 第二十一章

第二十一章

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

最长公共子序列

力扣链接

单个数组的子序列问题 – dp[i] -- 以nums[i] 为结尾的所有子序列中, xxx xxx. 然后状态转移方程根据最后一个位置的归属问题进行讨论
两个数组的子序列问题 – 以小见大, 分别分析nums1中的一个区间和 nums2的一个区间进行讨 --> dp[i][j] -- nums1中的[0, i] 区间以及 nums2中的 [0, j]区间内的所有子序列的组合中, 公共子序列的最大长度
状态转移方程 – 最后一个位置的具体情况
遍历顺序
初始化
需要使用左上角的情况 ⇒ dp表可以多开一行, 多开一列
但是dp表中使用原 nums1 和 nums2的情况就会出现偏差, 解决方法
1. 访问nums1 和 nums2里面的情况, 就要 －1
2. 可以在nums1, nums2前面添加一个 空格 ⇒ 使得dp表中的下标和 nums1 和 nums2中的下标一致化
⇒ 这样初始化就方便很多 , 都初始化为 0
返回值 — dp[i][j] -- nums1中的[0, i] 区间以及 nums2中的 [0, j]区间内的所有子序列的组合中, 公共子序列的最大长度 ⇒ 返回 dp[m][n]

访问 -1

class Solution {
public:
    int longestCommonSubsequence(string nums1, string nums2) 
    {
        int m = nums1.size();
        int n  = nums2.size();

        vector<vector<int>> dp(m+1, vector<int>(n+1));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                // 访问, -1
                if(nums1[i-1] == nums2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        return dp[m][n];
    }
};

添加空格

class Solution {
public:
    int longestCommonSubsequence(string nums1, string nums2) 
    {
        int m = nums1.size();
        int n  = nums2.size();

        vector<vector<int>> dp(m+1, vector<int>(n+1));

        // 访问, 添加空格
        nums1 = ' ' + nums1;
        nums2 = ' ' + nums2;

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(nums1[i] == nums2[j])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        return dp[m][n];
    }
};

不相交的线

力扣链接

这题的是 最长公共子序列 的变种题目, 求区间内的公共子序列的最长长度

两个数组的子序列问题 – 以小见大, 分别分析nums1中的一个区间和 nums2的一个区间进行讨 --> dp[i][j] -- nums1中的[0, i] 区间以及 nums2中的 [0, j]区间内的所有子序列的组合中, 公共子序列的最大长度
状态转移方程 – 最后一个位置的具体情况
遍历顺序
初始化
需要使用左上角的情况 ⇒ dp表可以多开一行, 多开一列
但是dp表中使用原 nums1 和 nums2的情况就会出现偏差, 解决方法
1. 访问nums1 和 nums2里面的情况, 就要 －1
2. 可以在nums1, nums2前面添加一个 空格 ⇒ 使得dp表中的下标和 nums1 和 nums2中的下标一致化
⇒ 这样初始化就方便很多 , 都初始化为 0
返回值 — dp[i][j] -- nums1中的[0, i] 区间以及 nums2中的 [0, j]区间内的所有子序列的组合中, 公共子序列的最大长度 ⇒ 返回 dp[m][n]

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) 
    {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> dp(m+1, vector<int>(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] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[m][n];
    }
};