最长公共子序列

这个与上篇笔记最大的不同就是子序列里的数可以不相邻,那么只需加入一个dp[i][j]的上和左的更新方向即可

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

不相交的线

其实求最大不相交数，就是一个从前到后的遍历顺序的问题，那就是两个相等的字符的相对顺序不变，那不就是求字符串的最长公共序列

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

最大子序和

本题尝试过用贪心求解，则只在当前元素为正的情况下去累加连续和

用动态规划求解，也就只有两个状态：dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0) return 0;
        vector<int> dp(nums.size());
        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]);//要么加上，要么从当前开始记算
            if(dp[i]>result) result=dp[i];
        }
        return result;
    }
};

判断子序列

编辑距离问题的入门问题

注意这里还是采用的用dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，以此来减少初始化数组的难度

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=t.size();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];
            }
        }
        if(dp[s.size()][t.size()]==s.size()) return true;
        return false;
    }
};