leetcode.674 最长连续递增序列

链接https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
解题思路：动态规划
1. 状态表示：f[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度是多少
2. 状态计算：
  如果 nums[i] 大于 nums[i-1] 则
  f[i] = max(f[i], f[i-1] + 1)
3. 起始状态：由状态表示可知，f[i] 的子序列至少有 nums[i] 这个数，所以将 f[i] 全部初始化为 1
注意：f[i] 表示以 nums[i] 结尾的最长递增子序列的长度是多少，而我们要求的答案是整个数组中最长连续递增子序列的长度，不一定是以nums[i] 结尾，所以不能直接返回 f[n-1] ，而应该用res每次更新最长的长度
leetcode解题代码

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1);

        for (int i = 0; i < n; i ++){
            if (i > 0 && nums[i] > nums[i - 1])
                f[i] = f[i - 1] + 1;
        }

        int res = 0;
        for (int i = 0; i < n; i ++) res = max(res, f[i]);

        return res;
    }
};

leetcode.300 最长递增子序列

链接https://leetcode.cn/problems/longest-increasing-subsequence/
解题思路：动态规划
1. 状态表示：f[i] 表示以 nums[i] 结尾的最长递增子序列的长度是多少
2. 状态计算：
  如果 nums[i] 大于 nums[j] 则
  f[i] = max(f[i], f[j] + 1)
3. 起始状态：由状态表示可知，子序列至少有 nums[i] 这个数，所以将 f[i] 全部初始化为 1，j 的下标为 0~i-1
注意：f[i] 表示以 nums[i] 结尾的最长递增子序列的长度是多少，而我们要求的答案是整个数组中最长递增子序列的长度，不一定是以 nums[i] 结尾，所以不能直接返回 f[n-1] ，而应该用res每次更新最长的长度
leetcode解题代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1);

        for (int i = 1; i < n; i ++){
            for (int j = 0; j < i; j ++){
                if (nums[i] > nums[j])
                    f[i] = max(f[i], f[j] + 1);
            }
        }
        
        int res = 0;
        for (int i = 0; i < n; i ++) res = max(res, f[i]);

        return res;
    }
};

leetcode.53 最大子数组和

链接https://leetcode.cn/problems/maximum-subarray/
解题思路：动态规划
1. 状态表示：f[i] 表示以 nums[i] 结尾的具有最大和的连续子数组
2. 状态计算：
  如果 nums[i] 小于 f[i-1]
  f[i] = f[i-1] + nums[i]
  如果 nums[i] 大于 f[i-1]
  f[i] = nums[i]
  两者取最大值，即
  f[i] = max(f[i-1] + nums[i], nums[i])
3. 起始状态：由状态计算可知，f[i] 由 f[i-1] 更新过来，f[0] 表示以 nums[0] 结尾的具有最大和的连续子数组，所以初始化
  f[0] = nums[0]
注意：f[i] 表示以 nums[i] 结尾的具有最大和的连续子数组，而我们要求的答案是整个数组中具有最大和的连续子数组，不一定是以 nums[i] 结尾，所以不能直接返回 f[n-1]，而应该用res每次更新最大和
leetcode解题代码

cclass Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        
        f[0] = nums[0];

        for (int i = 1; i < n; i ++){
            f[i] = max(f[i - 1] + nums[i], nums[i]);
        }

        int res = INT_MIN;
        for (int i = 0; i < n; i ++) res = max(res, f[i]);
        
        return res;
    }
};

leetcode.718 最长重复子数组

链接https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
解题思路：动态规划解法一
1. 状态表示：f[i][j] 表示以 nums1[i] 结尾的 nums1 与 nums2[j] 结尾的 nums2 公共的、长度最长的子数组的长度
2. 状态计算：
  如果 nums1[i] 等于 nums2[j] 则
  f[i][j] = f[i-1][j-1] + 1
3. 起始状态：
  由状态计算可知，f[i][j] 由 f[i-1][j-1] 转换过来，需要初始化第一行和第一列
  f[i][0] 表示以 nums1[i] 结尾的 nums1 与 nums2[0] 结尾的 nums2 公共的、长度最长的子数组的长度
  如果 nums1[i] 等于 nums2[0]，则f[i][0] = 1
  f[0][j] 表示以 nums1[0] 结尾的 nums1 与 nums2[j] 结尾的 nums2 公共的、长度最长的子数组的长度
  如果 nums1[0] 等于 nums2[j]，则f[0][j] = 1
注意：状态计算需要从 0 开始遍历，如果从 1 开始遍历res会无法更新第 0 行和第 0 列的值
leetcode解题代码

// 解法一
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> f(n, vector<int>(m));
        int res = 0;

        for (int i = 0; i < n; i ++)
            if (nums1[i] == nums2[0]) f[i][0] = 1;
        for (int j = 0; j < m; j ++)
            if (nums2[j] == nums1[0]) f[0][j] = 1;

        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++){
                if (nums1[i] == nums2[j] && i > 0 && j > 0)
                    f[i][j] = f[i - 1][j - 1] + 1;
                if (f[i][j] > res) res = f[i][j];
            }
        return res;
    }
};

解题思路：动态规划解法二
1. 状态表示：f[i][j] 表示以 nums1[i-1] 结尾的 nums1 与 nums2[j-1] 结尾的 nums2 公共的、长度最长的子数组的长度
2. 状态计算：
  与解法一相同
3. 起始状态：
  由状态计算可知，f[i][j] 由 f[i-1][j-1] 转换过来，需要初始化第一行和第一列
  f[i][0] 表示以 nums1[i-1] 结尾的 nums1 与 nums2[-1] 结尾的nums2 公共的、长度最长的子数组的长度
  nums2[-1] 表示空数组，与空数组的公共子数组的长度为 0
  所以f[i][0] = 0
  f[0][j] 表示以 nums1[-1] 结尾的 nums1 与 nums2[j-1] 结尾的nums2 公共的、长度最长的子数组的长度
  同理f[0][j] = 0
技巧：解法二相对于解法一明显在考虑初始化的时候代码会简单很多，二维dp都建议下标从 1 开始，在初始化的时候会简单很多
leetcode解题代码

// 解法二
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        int res = 0;

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++){
                if (nums1[i - 1] == nums2[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                if (f[i][j] > res) res = f[i][j];
            }
        return res;
    }
};

leetcode.1143 最长公共子序列

链接https://leetcode.cn/problems/longest-common-subsequence/
解题思路：动态规划解法一
1. 状态表示：f[i][j] 表示以 text1[i] 结尾的 text1 与 text2[j] 结尾的 text2 的最长公共子序列
2. 状态计算：
  如果 text[i] 等于 text[j] 则
  f[i][j] = f[i - 1][j - 1] + 1
  如果 text[i] 和 text[j] 不相等则有两种情况
  以 text1[i-1] 结尾的 text1 与 text[j] 结尾的 text2 的最长公共子序列为f[i - 1][j] 以 text[i] 结尾的 text1 与 text[j-1] 结尾的 text2 的最长公共子序列为 f[i][j - 1]
  两者取maxf[i][j] = max(f[i - 1][j], f[i][j - 1])
3. 起始状态：
  由状态计算可知，f[i][j] 由 f[i-1][j-1] 转换过来，需要初始化第一行和第一列
  f[i][0] 表示以 text1[i] 结尾的 text1 与 text[0] 结尾的 text2 的最长公共子序列
  如果 text1[i] 等于 text2[0]，则f[i][0] = 1
  如果 text1[i] 不等于 text2[0]，则f[i][0] = f[i - 1][0] f[0][j] 表示以 text[0] 结尾的 text1 与 text[j] 结尾的 text2的最长公共子序列
  如果 text1[0] 等于 text2[j]，则f[0][j] = 1
  如果 text1[i] 不等于 text2[0]，则f[i][0] = f[i - 1][0]
leetcode解题代码

// 解法一
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> f(n, vector<int>(m));

        if (text1[0] == text2[0]) f[0][0] = 1;
        for (int i = 1; i < n; i ++){
            if (text1[i] == text2[0]) f[i][0] = 1;
            else f[i][0] = f[i - 1][0];
        }
        for (int j = 1; j < m; j ++){
            if (text1[0] == text2[j]) f[0][j] = 1;
            else f[0][j] = f[0][j - 1];
        }
            

        for (int i = 1; i < n; i ++)
            for (int j = 1; j < m; j ++){
                if (text1[i] == text2[j])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        return f[n - 1][m - 1];
    }
};

解题思路：动态规划解法二
1. 状态表示：f[i][j] 表示以 text1[i-1] 结尾的 text1 与 text2[j-1] 结尾的 text2 的最长公共子序列
2. 状态计算：
  与解法一相同
3. 起始状态：
  由状态计算可知，f[i][j] 由 f[i-1][j-1] 转换过来，需要初始化第一行和第一列
  f[i][0] 表示以 text1[i-1] 结尾的 text1 与 text2[-1] 结尾的text2 的最长公共子序列
  text[-1] 表示空字符串，与空字符串的最长公共子序列的长度为0
  所以f[i][0] = 0
  f[0][j] 表示以 text1[-1] 结尾的 text1 与 text2[j] 结尾的text2 最长公共子序列的长度
  同理f[0][j] = 0
技巧：解法二相对于解法一明显在考虑初始化的时候代码会简单很多，二维dp都建议下标从 1 开始，在初始化的时候会简单很多
leetcode解题代码

// 解法二
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++){
                if (text1[i - 1] == text2[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        return f[n][m];
    }
};

leetcode.1035 不相交的线

链接https://leetcode.cn/problems/uncrossed-lines/
题意转换：最长公共子序列与上一题完全相同

leetcode.392 判断子序列

链接https://leetcode.cn/problems/is-subsequence/
解题思路：动态规划
1. 状态表示：f[i][j] 表示以 s[i-1] 结尾和 t[j-1] 结尾的最长子序列的长度
2. 状态计算：
  如果 s[i-1] 等于 t[j-1]
  以 s[i-1] 结尾和 t[j-1] 结尾的最长子序列的长度等于以 s[i-2] 结尾和 t[j-2] 结尾的最长子序列长度加 1
  f[i][j] = f[i-1][j-1] + 1
  如果 s[i-1] 不等于 t[j-1]
  以 s[i-1] 结尾和 t[j-1] 结尾的最长子序列的长度等于以 s[i-1] 结尾和 t[j-2] 结尾的最长子序列长度
  f[i][j] = f[i][j-1]
3. 起始状态：由状态计算可知，f[i][j] 由 f[i-1][j-1] 和 f[i][j-1] 更新过来，需要初始化第一行和第一列
  f[i][0] 表示以 s[i-1] 结尾和 t[-1] 结尾的最长子序列的长度
  t[-1] 为空字符串，最长子序列长度为 0
  同理 f[0][j] 也为 0
注意：由上两题可知动态规划子序列的题目采用解法二代码会更简洁，所以之后类似的题型都采用此解法
leetcode解题代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++){
                if (s[i - 1] == t[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = f[i][j - 1];
            }

        return f[n][m] == n;
    }
};

leetcode.115 不同的子序列

链接https://leetcode.cn/problems/distinct-subsequences/
解题思路：动态规划
1. 状态表示：f[i][j] 表示以 s[i-1] 结尾和 t[j-1] 结尾的子序列的个数
2. 状态计算：
  如果 s[i-1] 等于 t[j-1] 有两种情况
  例如baggg和bag，s[3] 和 t[2] 匹配，但 s[2] 和 t[2] 同样匹配
  可以取 s 和 t 的当前位进行匹配，s 和 t 同时回退一位f[i-1][j-1]
  也可以不取当前位进行匹配，s 回退一位f[i-1][j]
  所以f[i][j] = f[i-1][j-1] + f[i-1][j] 如果 s[i-1] 不等于 t[j-1] 只有一种情况
  不取当前位匹配，s 回退一位f[i-1][j]
  所以f[i][j] = f[i-1][j]
3. 起始状态：由状态计算可知，f[i][j] 由 f[i-1][j] 和 f[i-1][j-1] 更新过来，需要初始化第一行第一列
  f[i][0] 表示以 s[i-1] 结尾和 t[-1] 结尾的子序列的个数，空字符串是原字符串的一个子序列
  所以f[i][0] = 1
  f[0][j] 表示以 s[-1] 结尾和 t[j-1] 结尾的子序列的个数
  所以f[0][j] = 0
leetcode解题代码

class Solution {
public:
    typedef unsigned long long ULL;
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<ULL>> dp(n + 1, vector<ULL>(m + 1));
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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[n][m];
    }
};

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

链接https://leetcode.cn/problems/delete-operation-for-two-strings/
解题思路：动态规划
1. 状态表示：f[i][j] 表示使 word1[i-1] 结尾和 word2[j-1] 结尾的字符串相同所需的最小操作数
2. 状态计算：
  如果 word1[i-1] 等于 word2[j-1]
  则两个字符串都不需要操作，f[i][j] 最小操作数等于 f[i-1][j-1] 的最小操作数
  所以f[i][j] = f[i-1][j-1] 如果 word1[i-1] 不等于 word2[j-1] 有三种情况
  删除 word1 当前位，最小操作数为f[i-1][j] + 1
  删除 word2 当前位，最小操作数为f[i][j-1] + 1
  word1 和 word2 当前位都删除，最小操作数为f[i-1][j-1] + 2
  由状态表示可知f[i-1][j-1] + 1 = f[i-1][j]或f[i-1][j-1] + 1 = f[i][j-1]
  所以可以得出f[i][j] = min(f[i][j-1], f[i-1][j]) + 1
3. 起始状态：由状态计算可知，f[i][j] 由 f[i-1][j-1]、f[i-1][j]、f[i][j-1] 更新过来，需要初始化第一行第一列
  f[i][0] 表示以 word1[i-1] 结尾和 word2[-1] 结尾的字符串相同所需的最小步数，很明显需要将 word1 全部删除才能等于空字符串
  所以f[i][0] = i
  同理f[0][j] = j
  f[0][0] = 0
leetcode解题代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 1; i <= n; i ++) f[i][0] = i;
        for (int j = 1; j <= m; j ++) f[0][j] = j;

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++){
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else 
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            }
        return f[n][m];
    }
};

leetcode.72 编辑距离

链接https://leetcode.cn/problems/edit-distance/
解题思路：动态规划
1. 状态表示：f[i][j] 表示将 word1[i-1] 结尾的字符串转换成 word2[j-1] 结尾的字符串所需要的最少操作数
2. 状态计算：
  如果 word1[i-1] 和 word2[j-1] 相等，则不需要操作
  f[i][j] = f[i-1][j-1]
  如果 word1[i-1] 和 word2[j-1] 不相等，则有三种情况(均以 word1 进行操作)
  word1 和 word2 当前位需要被替换
  所需要的最少操作数为f[i-1][j-1] + 1
  word1 需要插入一个字符转换为 word2
  所需要的最少操作数为f[i][j-1] + 1
  word1 需要删除一位转换为 word2
  所需要的最少操作数为f[i-1][j] + 1
  三者取最小值
  所以f[i][j] = min(f[i-1][j-1], min(f[i][j-1], f[i-1][j])) + 1
3. 起始状态：由状态计算可知，f[i][j] 由 f[i-1][j-1]、f[i-1][j]、f[i][j-1] 更新过来，需要初始化第一行第一列
  f[i][0] 表示将 word1[i-1] 结尾的字符串转换成 word2[-1] 结尾的字符串所需要的最少操作数将 word1 转换成空串只能删除 word1 中所有字符
  所以f[i][0] = i 同理f[0][j] = j
leetcode解题代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 1; i <= n; i ++) f[i][0] = i;
        for (int j = 1; j <= m; j ++) f[0][j] = j;

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++){
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else f[i][j] = min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) + 1;
            }
        return f[n][m];
    }
};

leetcode.647 回文子串

链接https://leetcode.cn/problems/palindromic-substrings/
解题思路：动态规划
1. 状态表示：f[i][j] 表示字符串 s 在区间 [i, j] 是否是回文子串（闭区间，可以取到 i 和 j）
2. 状态计算：
  如果 s[i] 和 s[j] 不相等
  那么字符串 s 在区间 [i, j] 一定不是回文子串
  所以f[i][j] = false
  如果 s[i] 和 s[j] 相等，有两种情况
  如果字符串长度小于等于1，即空字符或字符本身一定是回文串
  如果字符串长度大于1，如果区间 [i+1, j-1] 是回文串，则区间 [i, j] 也是回文串
3. 起始状态：由状态计算可知，f[i][j] 由 f[i+1][j-1] 转化过来，所以遍历顺序应该是从下到上，从左到右，f[i][j] 初始化为false
leetcode解题代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n, false));
        int res = 0;

        for (int i = n - 1; i >= 0; i --)
            for (int j = i; j < n; j ++){
                if (s[i] == s[j]){
                    if (j - i <= 1){
                        res ++;
                        f[i][j] = true;
                    }
                    else if (f[i + 1][j - 1]){
                        res ++;
                        f[i][j] = true;
                    }
                }
            }
        return res;

    }
};

leetcode.5 最长回文子串

链接https://leetcode.cn/problems/longest-palindromic-substring/
解题思路：与上题类似
leetcode解题代码

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string res;
        vector<vector<bool>> f(n, vector<bool>(n, false));

        int maxLen = 0;
        int beginIndex = 0;
        for(int i = n - 1; i >= 0; i --) {
            for(int j = i; j < n; j ++) {
                if(s[i] == s[j]) {
                    if(j - i <= 1) {
                        f[i][j] = true;                  
                    }
                    else if(f[i + 1][j - 1]) {
                        f[i][j] = true;
                    }

                    if (f[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    beginIndex = i;
                    }
                }
            }
        }
        res = s.substr(beginIndex, maxLen);
        return res;
    }
};

leetcode.516 最长回文子序列

链接https://leetcode.cn/problems/longest-palindromic-subsequence/
解题思路：动态规划
1. 状态表示：f[i][j] 表示字符串 s 在区间 [i, j] 最长的回文子序列的长度
2. 状态计算：
  如果 s[i] 和 s[j] 不相等
  区间 [i, j] 最长的回文子序列的长度等于区间 [i+1, j] 最长的回文子序列的长度和区间 [i, j-1] 最长的回文子序列的长度的最大值所以f[i][j] = max(f[i+1][j], f[i][j-1])
  如果 s[i] 和 s[j] 相等
  区间 [i, j] 最长的回文子序列的长度等于区间 [i+1, j-1] 最长的回文子序列的长度 +2 所以f[i][j] = f[i+1][j-1] + 2
3. 起始状态：由状态计算可知，f[i][j] 由 f[i+1][j-1] 转化过来，所以遍历顺序应该是从下到上，从左到右，字符串本身为一个回文子序列，所以f[i][i] = 1
leetcode解题代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = 0; i < n; i ++) f[i][i] = 1;

        for (int i = n - 1; i >= 0; i --)
            for (int j = i + 1; j < n; j ++){
                if (s[i] == s[j])
                    f[i][j] = f[i + 1][j - 1] + 2;
                else 
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
            }
        return f[0][n - 1];
    }
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

动态规划-子序列系列.md

动态规划-子序列系列.md

leetcode.674 最长连续递增序列

leetcode.300 最长递增子序列

leetcode.53 最大子数组和

leetcode.718 最长重复子数组

leetcode.1143 最长公共子序列

leetcode.1035 不相交的线

leetcode.392 判断子序列

leetcode.115 不同的子序列

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

leetcode.72 编辑距离

leetcode.647 回文子串

leetcode.5 最长回文子串

leetcode.516 最长回文子序列

Files

动态规划-子序列系列.md

Latest commit

History

动态规划-子序列系列.md

File metadata and controls

leetcode.674 最长连续递增序列

leetcode.300 最长递增子序列

leetcode.53 最大子数组和

leetcode.718 最长重复子数组

leetcode.1143 最长公共子序列

leetcode.1035 不相交的线

leetcode.392 判断子序列

leetcode.115 不同的子序列

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

leetcode.72 编辑距离

leetcode.647 回文子串

leetcode.5 最长回文子串

leetcode.516 最长回文子序列