【动态规划算法练习】day14

摘星

发布于 2023-10-15 15:48:41

1350

发布于 2023-10-15 15:48:41

文章被收录于专栏：C/C++学习

一、97. 交错字符串

1.题目简介

97. 交错字符串给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串： s = s1 + s2 + … + sn t = t1 + t2 + … + tm |n - m| <= 1 交错是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + … 注意：a + b 意味着字符串 a 和 b 连接。

2.解题思路

3.代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size() + s2.size()) return false;
        vector<bool> v(s2.size() + 1, false);
        vector<vector<bool>> dp(s1.size() + 1, v);
        dp[0][0] = true;
        for(int i = 1;i <= s1.size(); ++i)
        {
            dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0];
        }
        for(int j = 1;j <= s2.size(); ++j)
        {
            dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1];
        }
        dp[0][0] = true;
        for(int i = 1;i <= s1.size(); ++i)
        {
            for(int j = 1;j <= s2.size(); ++j)
            {
                if((s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]))
                dp[i][j] = true;
            }
        }
        return dp[s1.size()][s2.size()];
    }
};

4.运行结果

二、712. 两个字符串的最小ASCII删除和

交错字符串、712. 两个字符串的最小ASCII删除和、718. 最长重复子数组

1.题目简介

712. 两个字符串的最小ASCII删除和给定两个字符串s1 和 s2，返回使两个字符串相等所需删除字符的 ASCII 值的最小和。

2.解题思路

3.代码

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        vector<int> v(s2.size() + 1, 0);
        vector<vector<int>> dp(s1.size() + 1, v);
        //dp[i][j]表示以i-1为结尾的字符串s1，和以j-1为结尾的字符串s2的公共子序列字符之和
        for(int i = 1;i <= s1.size(); ++i)
        {
            for(int j = 1;j <= s2.size(); ++j)
            {
                if(s1[i - 1] == s2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int sum = 0;
        for(auto& e : s1)
        {
            sum += e;
        }
        for(auto& e : s2)
        {
            sum += e;
        }
        return sum - 2 * dp[s1.size()][s2.size()];
    }
};

4.运行结果

三、718. 最长重复子数组

1.题目简介

718. 最长重复子数组给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。

2.解题思路

3.代码

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