3.动态规划.题目4

  • 开发
  • 17

3.动态规划.题目4

题目

32.最大子序和

题目链接
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
这题之前使用贪心算法解决过一次，现在使用动态规划方法再做一次。
1.dp[i]数组定义：==包括下标i（以nums[i]为结尾）==的最大连续子序列和为dp[i]；
2.递推关系：dp[i]只有两个方向可以推出来：1）dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和；2）nums[i]，即：从头开始计算当前连续子序列和
3.初始化：0下标，根据dp[i]的定义，很明显dp[0] = nums[0]。
4.遍历顺序：dp[i]依靠dp[i-1]递推出来，所以是从左往右遍历。

    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0) return 0;
        std::vector<int> dp(2, 0);
        dp[0]=nums[0];
        int res = nums[0];
        for(int i=1; i<nums.size(); i++){
            dp[i%2]=max(dp[(i-1)%2]+nums[i], nums[i]);
            if(dp[i%2]>res) res = dp[i%2];
        }
        return res;
    }

时间复杂度：O(n)；空间复杂度：O(n

33.判断子序列

题目链接
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
双指针方法：
这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况
1.dp数组定义：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]，且字符串长度t>=s
2.递推关系：if (s[i - 1] == t[j - 1])，即找到了一个相同的字符，那么dp[i][j] = dp[i - 1][j - 1] + 1；if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，与t的j-2字符比较的情况即：dp[i][j] = dp[i][j - 1];
3.初始化：0下标数组初始化为0
4.遍历顺序：根据递推公式，从字符串的前往后遍历。
在这里插入图片描述

	// 双指针法
    bool isSubsequence(string s, string t) {
        int j=0;
        for(int i=0; i<s.size(); i++){
            if(s[i]!=t[j]) i--;
            j++;
            if(j>t.size()) return false;
        }
        return true;
    }
	// 动态规划法
    bool isSubsequence(string s, string t) {
        std::vector<std::vector<int>> dp(2, std::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%2][j]=dp[(i-1)%2][j-1]+1;
                else dp[i%2][j]=dp[i%2][j-1];
            }
        }
        if(dp[s.size()%2][t.size()]==s.size()) return true;
        return false;
    }

时间复杂度：O(n × m)；空间复杂度：O(n × m)

34.不同的子序列-困难

题目链接
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。
在这里插入图片描述
1.dp[i][j]数组定义：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.递推关系：
1）当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成：用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]，即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]；一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]，所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。
2）当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
3.初始化：dp[i][0] 和dp[0][j]是一定要初始化的，dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。因此一定是1；dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数，因此一定是0；
4.遍历顺序：根据左上方和正上方推出来的；

    int numDistinct(string s, string t) {
        std::vector<std::vector<uint64_t>> dp(s.size()+1, std::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()];
    }

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

题目链接
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。输入: “sea”, “eat”；输出: 2；解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea”。
这题与34题的区别，这次是两个字符串可以相互删了。
1.dp[i][j]数组定义：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
2.递推关系：
1）当word1[i - 1] 与 word2[j - 1]相同的时候：dp[i][j] = dp[i - 1][j - 1]，
2）当word1[i - 1] 与 word2[j - 1]不相同的时候：在三种情况下取最小值 dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1})；但同时删除i-1, j-1的情况其实已经被其余两种情况所包含了，因此可以简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)；
3.初始化：递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i；dp[0][j]同理；

vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

4.遍历顺序：根据左上方、正上方、正左方推出来的。

    int minDistance(string word1, string word2) {
        std::vector<std::vector<int>> dp(word1.size()+1, std::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()];
    }

时间复杂度: O(nm)；空间复杂度: O(nm)

36.编辑距离

题目链接
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符；删除一个字符；替换一个字符。
编辑距离是用动规来解决的经典题目，这道题目看上去好像很复杂，但用动规可以很巧妙的算出最少编辑距离。
1.dp[i][j]数组定义：表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
2.递推关系：
1）if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，即dp[i][j] = dp[i - 1][j - 1]；
2）if (word1[i - 1] != word2[j - 1])此时需要编辑，删除元素dp[i][j] = dp[i - 1][j] + 1 或 dp[i][j] = dp[i][j - 1] + 1，添加元素（其实这个操作逻辑是和删除元素类似的），替换元素dp[i][j] = dp[i - 1][j - 1]；因此dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1。
3.初始化：dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]；那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i；
4.遍历顺序：从递推公式里看出，dp矩阵中一定是从左到右从上到下去遍历

    int minDistance(string word1, string word2) {
        std::vector<std::vector<int>> dp(word1.size()+1, std::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], min(dp[i][j-1], dp[i-1][j-1]))+1;
            }
        }
        return dp[word1.size()][word2.size()];
    }

时间复杂度: O(n m)；空间复杂度: O(n m)

37.回文子串

题目链接
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列
暴力解法：两层for循环，遍历区间起始位置和终止位置，然后还需要一层遍历判断这个区间是不是回文。所以时间复杂度：O(n^3)；
双指针法：思想是最短的回文子串其实有两种可能：单个字母，两个相同的字母，然后以该基本回文子串为基础，向两边扩展检查字母是否相等，因此可以通过一个for遍历string的每个字母，每次以string[i]或string[i]和string[i+1]为基础回文子串，再使用双指针方法检查两边的字母
动态规划
1.dp[i]数组定义：布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false；
2.递推关系：当s[i]与s[j]不相等，dp[i][j]一定是false；当s[i]与s[j]相等时，1）下标i 与 j相同，同一个字符例如a，当然是回文子串，2）下标i 与 j相差为1，例如aa，也是回文子串，3）下标：i 与 j相差大于1的时候，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
3.初始化：不能刚开始就全都匹配上了，所以dp[i][j]初始化为false。
4.遍历顺序：从递推公式可以看出是从下到上，左到右进行遍历。

	// 动态规划方法
    int countSubstrings(string s) {
        std::vector<std::vector<bool>> dp(s.size(), std::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) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } 
                    else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
    // 双指针方法
    int extend(const string& s, int i, int j, int n){
        int res = 0;
        while(i>=0 && j<n && s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
    int countSubstrings(string s) {
        int res = 0;
        for(int i=0; i<s.size(); i++){
            res += extend(s, i, i, s.size());
            res += extend(s, i, i+1, s.size());
        }
        return res;
    }

时间复杂度：O(n^2)； 空间复杂度：O(n^2)

38.最长回文序列

题目链接
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
与37题的区别在于回文子串是连续的，而现在这题的回文序列是不要求连续的。
1.dp[i][j]数组定义：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
2.递推关系：如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2；如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列，dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
3.初始化：全部置0也可以，当i=j时，回文子串的最大长度是1
4.遍历顺序：从递推关系看出从下到上，从左到右
在这里插入图片描述

	// 动态规划法
    int longestPalindromeSubseq(string s) {
        std::vector<std::vector<int>> dp(s.size(), std::vector<int>(s.size(), 0));
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i; j<s.size(); j++){
                if(s[i]==s[j]){
                    if(i==j) dp[i][j]=1;
                    else 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];
    }

时间复杂度: O(n^2)；空间复杂度: O(n^2)

动态规划总结

代码随想录中的题目包括：

  1. 基础题目
  2. 背包问题
  3. 打家劫舍
  4. 股票问题
  5. 子序列问题
    在这里插入图片描述

关于动规，还有 树形DP（打家劫舍系列里有一道），数位DP，区间DP ，概率型DP，博弈型DP，状态压缩dp等等等，这些我就不去做讲解了，面试中出现的概率非常低，熟悉掌握以上5大类方法足够应对面试。

在这里插入图片描述
以上图是这个图是 代码随想录知识星球 (opens new window)成员：青 (opens new window)，所画，总结的非常好。

阅读全部

相关推荐

  3. 动态规划入门题目

    2024-07-22 02:12:04       58 阅读

  6. Part 4.3 区间动态规划

    2024-07-22 02:12:04       20 阅读

  8. 【LeetCode】动态规划--题目练习

    2024-07-22 02:12:04       36 阅读

  9. [LeetCode]-动态规划-4

    2024-07-22 02:12:04       41 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 02:12:04       52 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 02:12:04       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-22 02:12:04       45 阅读

  19. Python语言-面向对象

    2024-07-22 02:12:04       55 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-22 02:12:04       50 阅读

热门阅读

  2. C++ Primer：4.4 赋值运算符

    2024-07-22 02:12:04       20 阅读

  8. ubuntu 上安装软件

    2024-07-22 02:12:04       19 阅读

  9. ubuntu系统下安装配置 8.0.37的MySQL

    2024-07-22 02:12:04       15 阅读

  10. Keras和Pytorch输入图像的张量维度

    2024-07-22 02:12:04       17 阅读

  13. ASP.NET Core在启动过程中使用数据库实例的几种方式

    2024-07-22 02:12:04       18 阅读

  15. 中介子方程六十五

    2024-07-22 02:12:04       20 阅读

  18. linux命令

    2024-07-22 02:12:04       17 阅读

  20. 1186. 删除一次得到子数组最大和

    2024-07-22 02:12:04       19 阅读
  21. GPT-LLM

    GPT-LLM

    2024-07-22 02:12:04      17 阅读

  22. 【开源库学习】libodb库学习（二）

    2024-07-22 02:12:04       16 阅读

  26. 【C++】C++中使用using namespace std；时，如何避免潜在的名称冲突问题？

    2024-07-22 02:12:04       19 阅读