代码随想录算法训练营刷题复习3：动态规划——子序列问题

作者：木道寻08 | 2024-08-13 03:31:58

踩

子序列问题

包含四个子问题：子序列（不连续）、子序列（连续）、编辑距离、回文

子序列（不连续）

300.最长递增子序列
定义dp数组，问什么dp的定义就设什么，
更新dp[i]的值，两层循环，第二层循环遍历i之前出现过的元素
1143.最长公共子序列
做题的时候能找到思路，有些小细节忽略掉但是能在写的过程中找出来改正
1035.不相交的线
印象很深刻，主要是把这个题的问法换一种（换成最长相等元素子序列），差不多是上面俩题的结合体（主要是第二个题的代码思路，第一个题的判断条件）

300.最长递增子序列

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

1143.最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //声明dp数组的大小时，忽略了i-1 j-1导致越界的问题，后面发现改正了
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));

        int result=0;
        //考虑 i-1 j-1这个下标不能越界问题，i和j下标都是从1开始，
        for(int i=1;i<=text1.size();i++) {
            for(int j=1;j<=text2.size();j++) {
//                对于字符串来说，首元素下标仍然为0，以下元素比对时需要用i-1
                if(text1[i-1]==text2[j-1])
                    dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]);
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-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
18
19
20
21
22

1035.不相交的线
上面俩题的结合体（主要是第二个题的代码思路，第一个题的判断条件）
印象很深刻，主要是把这个题的问法换一种（换成最长相等元素子序列）

class Solution {
public:
    int maxUncrossedLines(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] = max(dp[i-1][j-1]+1, dp[i][j]);
                }
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-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
18
19
20

子序列（连续）

674.最长连续递增序列

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

718.最长重复子数组

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

        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

53.最大子序和

dp更新的逻辑：max(dp[i-1]+nums[i], nums[i])看继承这个值与从这个值重新开始哪个更值

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

编辑距离

这个系列的题，定义dp数组的时候都需要多出来一行一列并且需要进行初始化。

392.判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()==0)
            return true;
        else if(t.size()==0)
            return false;
    //原本想把dp数组设置为bool类型，但是想不出后面怎么做了
    //转换一下思想，把他转化为t字符串与s字符串的公共元素的个数，最后比对是否公共元素个数为s字符串的长度，返回对应值就可
        vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1,false));

        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];   //如果不是的话，就"删除"t当前这个元素，继承上一个元素值
                }
            }
        }
        if(dp[s.size()][t.size()]==s.size())
            return true;
        else
            return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

115.不同的子序列
这个题还是要复习

class Solution {
public:
    int numDistinct(string s, string t) {
        // unsigned long long
        vector<vector<unsigned long long>> dp(s.size()+1,vector<unsigned long long>(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]) {
                    //①用s[i-1]  +  ②不用s[i-1]
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
                else {
                    //到这里走不了了，继承s的上一个下标对应的dp值 只修改i
                    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
20
21
22

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        if(word1.size()==0)
            return word2.size();
        else if(word2.size()==0)
            return word1.size();
        //因为对dp第0行和第0列进行了初始化，所以不需要将其他值初始化为INT_MAX，赋值0就可以了
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
        for(int i=1;i<=word1.size();i++) {
            dp[i][0]=i;
        }
        for(int j=1;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
23
24
25
26
27
28

72.编辑距离

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],min(dp[i-1][j],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

回文

647.回文子串
这里虽然也用二维dp数组，但是不需要对数组的大小+1，因为这个dp数组的含义和上面编辑距离类型的dp含义不同。
遇到元素相同时，根据下标的间隔大小分两种情况，在得到dp[i][j]为true的时候 result++；
516.最长回文子序列
dp数组中，i 和 j 的遍历顺序分别为 i从底到头、j从i到尾，dp数组的对角线元素初始化为1，直接把上一题的元素下标差给限定了。

647.回文子串
遇到元素相同时，根据下标的间隔大小分两种情况，在得到dp[i][j]为true的时候 result++；

class Solution {
public:
    int countSubstrings(string s) {
        if(s.size()<=1)
            return s.size();
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));

        int result=0;
        for(int i=s.size()-1;i>=0;i--) {
            for(int j=i;j<s.size();j++) {
                if(s[i]==s[j]) {
                    if(j-i<=1) {
                        dp[i][j]=true;
                        result++;
                    }
                    else {
                        if(dp[i+1][j-1]) {
                            dp[i][j] = true;
                            result++;
                        }
                    }

                }
            }
        }
        return result;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

516.最长回文子序列
dp数组中，i 和 j 的遍历顺序分别为 i从底到头、j从i到尾，dp数组的对角线元素初始化为1，直接把上一题的元素下标差给限定了。

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/972940