代码随想录day52:动态规划子序列问题part1

300.最长递增子序列

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
子序列问题是动态规划解决的经典问题，当前下标i的递增子序列长度，其实和i之前的下表j的子序列长度有关系。
解题思路：dp[i]代表以nums[i]结尾的递增子序列长度
那么每次更新dp[i]都是在比较结尾nums[i]与前边所有元素的大小。如果比前边大，那么就是dp[j]+1。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int result=1;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]) dp[i]=max(dp[i],dp[j]+1);
            }
        if(result<dp[i]) result=dp[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最长连续递增序列

注意题干中连续的要求，所以直接一个循环nums[i-1]和nums[i]即可解决问题。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int result=1;
        for(int i=1;i<nums.size();i++){
            if(nums[i]>nums[i-1]) dp[i]=dp[i-1]+1;
            if(result<dp[i]) result=dp[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

718.最长重复子数组

二维数组。dp[i][j]代表的是比较到nums1[i-1],nums2[j-1]的最长重复子序列。注意等于号。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        int result=0;
        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;
                }
                if(result<dp[i][j]) result=dp[i][j];
            }
        }
        return result;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一维数组要从后往前遍历才不会被错误相加。

1143.最长公共子序列

        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()];
1
2
3
4
5
6
7
8
9
10
11

1035.不相交的线

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！等同于上一题

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        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()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

53.最大子序列和

之前用贪心算过，从头开始算和，一旦遇到负数，立马放弃。
dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
dp[0] = nums[0]
注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。所以在递推公式的时候，可以直接选出最大的dp[i]。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        if(nums.size()==1) return dp[0];
        int result=dp[0];//INT_MIN
        for(int i=1;i<nums.size();i++){
            dp[i]=max(nums[i]+dp[i-1],nums[i]);
            if(result<dp[i]) result=dp[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意！！result的初始化不能是0，对于负数不行，也不能是INT_MIN对于【-1，-2】这种含有两个元素的不适合

392.判断子序列

这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。所以掌握本题的动态规划解法是对后面要讲解的编辑距离的题目打下基础。
dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。
if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）
if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的，区别就是 本题 如果删元素一定是字符串t，而 1143.最长公共子序列 是两个字符串都可以删元素。

115.不同的子序列

1.dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.递推公式：如果s[i-1],t[j-1]相等的时候，是有都去掉相等的尾元素情况和只去掉s尾字符的情况。

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1,0));
        for(int i=0;i<=s.size();i++){
            dp[i][0]=1;
        }
        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] + dp[i - 1][j];
                }
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

方法一：115.不同的子序列，从只删除s字符串，到删除两个字符串

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word1.size();i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=word2.size();j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.size();i++){
            for(int j=1;j<=word2.size();j++){
                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]+1);
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

也可以用最长公共长度为基础，找到两个字符串的公共长度其余的就是要删除的

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=1;i<=word1.size();i++){
            for(int j=1;j<=word2.size();j++){
                if(word1[i-1] == word2[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 word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

72.编辑距离

这次不仅可以删除了，还可以插入，替换。
编辑距离是用动规来解决的经典题目
1.确定dp数组（dp table）以及下标的含义dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
2.递推公式：增删改操作数都是1，跟删除一样，所以可以当作删除处理。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word1.size();i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=word2.size();j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.size();i++){
            for(int j=1;j<=word2.size();j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }
                else{
                    dp[i][j]=min(min(dp[i-1][j-1]+1,dp[i-1][j]+1),dp[i][j-1]+1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23