代码随想录算法训练营第53天 | 1143.最长公共子序列, 1035.不相交的线, 53.最大子序和(动态规划)

1143.最长公共子序列

代码随想录链接

题目

LeetCode-1143.最长公共子序列

给定两个字符串, 返回两个字符串的最长公共子序列的长度.

题目分析

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[i][j]代表text1[0~i]和text2[0~j]部分最长公共子序列的长度.

• 确定递推公式

  分为text1[i]和text2[j]相同和不相同的情况:

  若相同, 则dp[i][j] = dp[i - 1][j - 1] + 1

  若不同, 则dp[i][j]应该取text1[0~(i-1)]和text2[0~j]的最长公共子序列的长度及text1[0~i]和text2[0~(j-1)]的最大值, 即dp[i][j] = max(dp[i-1][j], dp[i][j-1])

• dp数组的初始化

  对于i或j为0的位置, 需要进行判断是否赋值为1.

• 遍历顺序

  两层循环, 一层用来遍历text1, 一层用来遍历text2.

题解

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), 0));
        for (int i = 0; i < text1.size(); i++)
            if (text1[i] == text2[0])
                dp[i][0] = 1;
        for (int j = 0; j < text2.size(); j++)
            if (text2[j] == text1[0])
                dp[0][j] = 1;
        for (int i = 0; i < text1.size(); i++)
            for (int j = 0; j < text2.size(); j++)
                if (text1[i] == text2[j] && i && j)
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else if (text1[i] != text2[j] && i && j)
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                else if (text1[i] != text2[j] && i)
                    dp[i][j] = dp[i - 1][j];
                else if (text1[i] != text2[j] && j)
                    dp[i][j] = dp[i][j - 1];
        return dp.back().back();
    }
};

1035.不相交的线

代码随想录链接

题目

LeetCode-1035.不相交的线

给定两个数组, 在两个数组中相等的数之间一对一进行画线, 求最多能画多少条不相交的线.

题目分析

说是画线, 其实就还是找最长公共子序列的长度, 因为最长公共子序列中的每一位都可以能一一对应且画线不相交.

题目分析见上一题.

题解

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        for (int i = 1; i <= nums1.size(); i++)
            for (int j = 1; j <= nums2.size(); 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.back().back();
    }
};

53.最大子序和(动态规划)

代码随想录链接

题目

LeetCode-53.最大子序和

给定一个整数数组, 找到一个具有最大和的连续子数组并返回其和.

题目分析

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[i]表示nums[0~i]中最大连续子序列和.

• 确定递推公式

  dp[i]的来源有两个:

  一个是nums[i]加入前面的子数组, 另一个是重新开始计算子序列.

  有: dp[i] = max(dp[i - 1] + nums[i], nums[i])

• dp数组的初始化

  dp[0]应初始化为nums[0], 因为题目中给定了子序列至少有一个数字, dp数组其他位置应初始化为INT_MIN

• 确定遍历顺序

题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(dp[i], result);
        }
        return result;
    }
};