子序列（不连续）

300.最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return n;
		// 1.定义dp数组以及下标的含义
		// dp[i]表示0-i的数组以第i个数字为结尾的最长递增子序列的数量为dp[i]
		// 3.dp数组初始化
        vector<int> dp(n,1);
        int result{0};
        // 4.确定遍历顺序，暴力遍历所有子序列
        for(int i{1};i<n;++i){
            for(int j{};j<i;++j){
            	// 2.确定递推公式
                if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j] + 1);
            }

            if(dp[i] > result) result = dp[i];
        }

        return result;
    }
};

1143.最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int l1 = text1.size();
        int l2 = text2.size();
		// 1.确定dp数组以及下标的含义
		// dp[i][j]表示长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        vector<vector<int>> dp(l1+1,vector<int>(l2+1));
        // 3.dp数组初始化
        int result{};
        // 4.确定遍历顺序，暴力遍历两个字符串的子序列
        for(int i{1};i<=l1;++i){
            for(int j{1};j<=l2;++j){
            	// 2.确定递推公式
                if(text1[i-1] == text2[j-1]){ // 判断下标为i-1与j-1的字符是否相等
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }

                if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

1035.不相交的线

class Solution {
public:
	// 关键是要想到：求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();

        int result{};
        vector<vector<int>> dp(len1+1,vector<int>(len2+1));
        for(int i{1};i<=len1;++i){
            for(int j{1};j<=len2;++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]);

                if(dp[i][j] > result) result = dp[i][j];
            }
        }

        return result;
    }
};

673.最长递增子序列个数

class Solution {
public:
	// 300.最长递增子序列的扩展
    int findNumberOfLIS(vector<int> &nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        // 1.定义dp数组以及下标的含义
        // dp[i]  表示以 nums[i] 结尾的最长上升子序列的长度，
        // cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。
		// 3.dp数组初始化，全部初始化为1
        vector<int> dp(n,1), cnt(n,1);
        // 3.确定遍历顺序，暴力遍历所有子序列
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
            	// 2.确定递推公式
                if (nums[i] > nums[j]) {
                	// dp[i] = max(dp[i],dp[j] + 1)
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j]; // 重置计数
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            // 获取最大值
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
};

子序列（连续）

674.最长连续递增序列

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = 1;
        // 1.确定dp数组以及下标的含义
        // dp[i]表示以第i个数字为结束的子序列的最长连续递增子序列的长度为dp[i]
        // 3.dp数组初始化，都初始化为1
        vector<int> dp(nums.size() ,1);
        // 确定遍历顺序：从小到大依次遍历
        for (int i = 0; i < nums.size() - 1; i++) {
        	// 2.确定递推公式
            if (nums[i + 1] > nums[i]) {
                dp[i + 1] = dp[i] + 1;
            }
            if (dp[i + 1] > result) result = dp[i + 1];
        }
        return result;
    }
};

718.最长重复子数组

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
    	int len1 = nums1.size();
        int len2 = nums2.size();
        // 1.确定dp数组以及下标的含义
        // dp[i][j]表示数组1下标[0,i-1] 与 数组2下标[0,j-1]的最长重复子数组的长度为dp[i][j]
        // 3.dp数组初始化
        vector<vector<int>> dp (len1  + 1, vector<int>(len2  + 1, 0));
        int result = 0;
        // 4.确定遍历顺序，暴力遍历两个数组的子序列
        for (int i = 1; i <= len1 ; i++) {
            for (int j = 1; j <= len2 ; j++) {
            	// 2.确定递推公式
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

53.最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        // 1.定义dp数组以及下标的含义
        // dp[i],以第i个数为结尾的子数组的最大和为dp[i]
        vector<int> dp(n+1);
        int result{nums[0]};
        // 3.dp数组初始化
        dp[0] = nums[0];
        // 4.确定遍历顺序
        for(int i{1} ;i < n;++i){
        	// 2.确定递推公式
            dp[i] = max(dp[i-1] + nums[i],nums[i]);
            if(dp[i] > result) result = dp[i];
        }
        return result;
    }
};

编辑距离

编辑距离问题核心在：递推公式推导与dp数组初始化

392.判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int lS = s.size();
        int lT = t.size();
		// 1.定义dp数组以及数组下标的含义
		// dp[i][j] 表示字符串s [0,i]与字符串t[0,j]的相同子序列的长度的长度为dp[i][j]
		// 3.dp数组初始化
        vector<vector<int>> dp(lS+1,vector<int>(lT+1));
        // 4.确定遍历顺序，暴力遍历
        for(int i{1};i<=lS;++i){
            for(int j{1};j<=lT;++j){
            	// 2.确定递推公式
                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[lS][lT] == s.size();
    }
};

115.不同的子序列

class Solution {
public:
    using LL = unsigned long long;// 防止溢出
    int numDistinct(string s, string t) {
        int lenS = s.size();
        int lenT = t.size();
		// 1.确定递推公式
		// dp[i][j]表示：字符串s[0,i]与字符串t[0,j]中，s的子序列中t的个数为dp[i][j]
        vector<vector<LL>> dp(lenS+1,vector<LL>(lenT+1));
        // 3.dp数组初始化
        for(int i{};i<lenS;++i) dp[i][0] = 1;
        for(int j{1};j<lenT;++j) dp[0][j] = 0;
		// 4.确定遍历顺序：暴力遍历
        for(int i = 1;i<=lenS;++i){
            for(int j = 1;j<=lenT;++j){
            	// 2.确定递推公式
            	// s[i - 1] 与 t[j - 1]相等： dp[i-1][j-1]+dp[i-1][j]
				// s[i - 1] 与 t[j - 1] 不相等： dp[i-1][j]
                if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[lenS][lenT];
    }
};

583.两个字符串的删除操作

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
		// 1.定义dp数组和数组下标的含义
		// dp[i][j]表示字符串word1[0,i]与字符串word2[0,j],使得 word1 和  word2 相同所需的最小步数为dp[i][j]
        vector<vector<int>> dp(len1+1,vector<int>(len2+1));
		// 3.dp数组初始化
        for(int i{};i<=len1;++i) dp[i][0] = i;
        for(int j{};j<=len2;++j) dp[0][j] = j;
		// 4.确定遍历顺序：暴力遍历子序列
        for(int i{1};i<=len1;++i){
            for(int j{1};j<=len2;++j){
            	// 2.确定递推公式
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j-1] + 2,min(dp[i-1][j] + 1,dp[i][j-1] + 1));
            }
        }

        return dp[len1][len2];
    }
};

72.编辑距离

class Solution {
public:
	// 583.两个字符串的删除操作的变形
    using LL = unsigned long long;
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
		// 1.定义dp数组以及数组下标的含义
		// dp[i][j]:字符串word1[0,i] 与word2[0,j]，将 word1 转换成 word2 所使用的最少操作数为dp[i][j]
        vector<vector<LL>> dp(len1+1,vector<LL>(len2+1));
        // 3.dp数组初始化
        for(int i{};i<=len1;++i) dp[i][0] = i;
        for(int j{};j<=len2;++j) dp[0][j] = j;
        // 4.确定遍历顺序
        for(int i{1};i<=len1;++i){
            for(int j{1};j<=len2;++j){
            	// 2.确定递推公式
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min({dp[i-1][j-1],dp[i][j-1],dp[i-1][j]}) + 1;
                }
            }
        }

        return dp[len1][len2];
    }
};

回文

647.回文子串

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.size();
        int result{};
        // 1.确定dp数组以及下标的含义
        // dp[i][j]:表示区间范围[i,j] 的子串是否是回文子串，如果是dp[i][j]为true，否则为false
        // 3.dp数组初始化
        vector<vector<bool>> dp(len,vector<bool>(len,false));
		// 4.确定遍历顺序：从下到上，从左到右遍历，保证dp[i + 1][j - 1]都是经过计算
        for(int i = len-1;i>=0;--i){
            for(int j=i;j<len;++j){
            	// 2.确定递推公式
                if(s[i] == s[j]){
                    if(j-i <= 1){
                        result++;
                        dp[i][j] = true;
                    }else if(dp[i+1][j-1]){
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }

        return result;
    }


};

516.最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();
        // 1.确定dp数组以及数组下标的含义
        // dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
        vector<vector<int>> dp(len,vector<int>(len));
		// 3.dp数组初始化
        for(int i{};i<len;++i) dp[i][i] = 1;
		// 4.确定遍历顺序：遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的
        for(int i = len-1;i>=0;--i){
            for(int j = i+1;j<len;++j){
            	// 2.确定递推公式
                if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                	// 只加入j或者i表示删除字符操作
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

        return dp[0][len-1];
    }
};