1143. 最长公共子序列 – 力扣（LeetCode）

csdn推荐

题1： 指路：1143. 最长公共子序列 - 力扣（LeetCode） 思路与代码：

类似于最长重复子数组，我们依旧定义一个二维数组dp[i][j]，其含义为从0到以i-1结尾的nums1数组和从0到j-1结尾的nums2数组的最长公共子序列的长度。如果nums1中的数和nums2的数相等时dp数组得到一个结果，即为dp[i][j]=dp[i-1][j-1]+1，当两个数组中的数值不相等时，就将行或列后退一位取二者较大值，即为dp[i][j]=max(dp[i-1][j], dp[i][j-1])。相似的，我们将dp数组结尾定义为i-1和j-1，那么这里就可以直接初始化为0。最后返回即可。代码如下：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
    vector<vector> dp(text1.size() + 1, vector(text2.size() + 1, 0));
    for (int i = 1; i <= text1.size(); i++) {
        for (int j = 1; j <= text2.size(); j++) {
            if (text1[i - 1] == text2[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[text1.size()][text2.size()];
    }
};

题2： 指路：1035. 不相交的线 - 力扣（LeetCode） 思路与代码：

这个题跟上一个题大同小异。代码如下：

class Solution {
public:
    int maxUncrossedLines(vector& nums1, vector& nums2) {
    vector<vector> dp(nums1.size() + 1, vector(nums2.size() + 1));
    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[nums1.size()][nums2.size()];
    }
};

题3： 指路：53. 最大子数组和 - 力扣（LeetCode） 思路与代码：

class Solution {
public:
    int maxSubArray(vector& nums) {
    vector dp(nums.size());
    dp[0] = nums[0];
    int sum = dp[0];
    for (int i = 1; i  sum) {
            sum = dp[i];
        } 
    }
    return sum;
    }
};

文章来源:https://blog.csdn.net/m0_74174715/article/details/139999535