【c++刷题笔记-动态规划】day44：1143.最长公共子序列 、 1035.不相交的线 、 53. 最大子序和 、392.判断子序列

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

思路：动态规划，分为三种状态。当两个字符相同时同时增长，不相同时由i-1的和j-1的状态进行推导

重点： 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]);
            }

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

1035. 不相交的线 - 力扣（LeetCode）

思路：同上，理解题意就是最长公共子序列

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

 53. 最大子数组和 - 力扣（LeetCode）

思路：判断每个以nums[i]结尾的数的累加和，找最大值

重点：dp[i]=max(dp[i-1]+nums[i],nums[i]);

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int>dp(n,0);
        dp[0]=nums[0];
        int ans=dp[0];//最初的最大和
        for(int i=1;i<n;i++){
            //因为累加和可能为负数
            dp[i]=max(dp[i-1]+nums[i],nums[i]);//当以前的累加和与现在的数比较
            if(dp[i]>ans){
                ans=dp[i];
            }
        }
        return ans;
    }
};

392. 判断子序列 - 力扣（LeetCode）

思路：依次判断s的字符是否为t的子序列，当最长子序列长度为s的长度时，表示s是t的子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m=s.size(),n=t.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s[i-1]==t[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;//同时增加长度
                }else{
                    dp[i][j]=dp[i][j-1];//相当于长字符串删除一个字符后的前一个状态
                }
            }
        }
        return dp[m][n]==m?true:false;//最长等于m的长度就说明s是t的子序列
    }
};

总结

子序列问题，判断dp数组的递推就行了

原文地址：https://blog.csdn.net/qq_48662659/article/details/140539853

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！