两个数组的dp问题

  • 开发
  • 14

目录

最长公共子序列

不相交的线

不同的子序列

通配符匹配

正则表达式匹配

交错字符串

两个字符串的最小ASCII删除和

最长重复子数组

声明：接下来主要使用动态规划来解决问题！！！

最长公共子序列

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

状态表示：dp[i][j]表示字符串1的[0,i]区间和字符串2的[0,j]区间内的所有公共子序列的最长的长度.

状态转移方程：if(s1[i]==s2[j])     dp[i][j]=dp[i-1][j-1]+1；

                         else     dp[i][j]=max(dp[i-1][j],dp[i][j-1]).

初始化：不用初始化。

填表顺序：从左往右。

返回值：dp[m][n].

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;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[m][n];
    }
};





//或者下面的




class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        text1=' '+text1;
        text2=' '+text2;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        return dp[m][n];
    }
};
不相交的线

题目

思路

以例2为例，

通过观察不难发现，实则是找两个数组的最长公共子数组，与上一道题最长公共子序列如出一辙。

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

状态表示：dp[i][j]表示数组1的[0,i]区间和数组2的[0,j]区间内的所有公共子数组的最长的长度.

状态转移方程：if(nums1[i]==s2[j])     dp[i][j]=dp[i-1][j-1]+1；

                         else     dp[i][j]=max(dp[i-1][j],dp[i][j-1]).

初始化：不用初始化。

填表顺序：从左往右。

返回值：dp[m][n].

代码

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(),n=nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;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[m][n];
    }
};
不同的子序列

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

状态表示：dp[i][j]表示s[0,i]区间内有多少种t[0,j]区间字符串。

状态转移方程：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]【后者必须满足s[i]==t[j]】

初始化：dp[i][0]=1,第一列全都初始化为1.

返回值：dp[m][n].

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int m=s.size(),n=t.size();
        vector<vector<double>> dp(m+1,vector<double>(n+1));
        for(int i=0;i<=m;i++)
            dp[i][0]=1;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                dp[i][j]=dp[i-1][j];
                if(s[i-1]==t[j-1])
                    dp[i][j]+=dp[i-1][j-1];
            }
        return dp[m][n];
    }
};




//或者下面的代码




class Solution {
public:
    int numDistinct(string s, string t) {
        int m=s.size(),n=t.size();
        s=' '+s;
        t=' '+t;
        vector<vector<double>> dp(m+1,vector<double>(n+1));
        for(int i=0;i<=m;i++)
            dp[i][0]=1;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                dp[i][j]=dp[i-1][j];
                if(s[i]==t[j])
                    dp[i][j]+=dp[i-1][j-1];
            }
        return dp[m][n];
    }
};
通配符匹配

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

状态表示：dp[i][j]表示字符串p[0,j]区间字符串是否能匹配字符串s[0,i]区间字符串。

针对p[j]=='*'，化简

【1】数学方法

【2】分析法

可以先让'*’匹配一个s字符串末尾字符，但是不消掉'*'

得

状态转移方程：

                if(p[j-1]!='*') dp[i][j]=(p[j-1]=='?' || p[j-1]==s[i-1]) && dp[i-1][j-1];

                else dp[i][j]=dp[i-1][j] || dp[i][j-1];

初始化：

第一列除去[0,0]位置之外全都为fasle,

第一行除去[0,0]位置之外，初始化规则：当字符串p[0,j]区间含不为'*'字符，后边都为false，否则为true.

填表顺序：从上往下，从左往右。

返回值：dp[m][n].

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            if(p[i-1]=='*') dp[0][i]=true;
            else break;
        }
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(p[j-1]!='*') dp[i][j]=(p[j-1]=='?' || p[j-1]==s[i-1]) && dp[i-1][j-1];
                else dp[i][j]=dp[i-1][j] || dp[i][j-1];
            }
        return dp[m][n];
    }
};



//或者为下面的代码



class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        // dp[0][0]=true;
        for(int i=0;i<=n;i++){
            bool flag=true;
            for(int j=0;j<i;j++){
                if(p[j]!='*') flag=false;
            }
            dp[0][i]=flag;
        }
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(p[j-1]==s[i-1]) dp[i][j]=dp[i-1][j-1];
                else if(p[j-1]=='?') dp[i][j]=dp[i-1][j-1];
                else if(p[j-1]=='*') dp[i][j]=dp[i-1][j] || dp[i][j-1];
            }
        return dp[m][n];
    }
};
正则表达式匹配

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

状态表示：dp[i][j]表示字符串p[0,j]区间字符串是否能匹配字符串s[0,i]区间字符串。

针对p[j]=='*'，化简

【1】数学方法

【2】分析法

可以先让'*’和前一个字符匹配一个s字符串末尾字符，但是不消掉'*'和前一个字符

状态转移方程：

                if(p[j-1]=='*') dp[i][j]=((p[j-2]==s[i-1] || p[j-2]=='.') && dp[i-1][j]) || dp[i][j-2];

                else dp[i][j]=(p[j-1]=='.' || p[j-1]==s[i-1]) && dp[i-1][j-1];

初始化：

第一列除去[0,0]位置之外全都为fasle,

第一行除去[0,0]位置之外，初始化规则：当字符串p[0,j]区间偶数位置都为'*'字符，则为false，其余位置为false，否则之后都为true.

填表顺序：从上往下，从左往右。

返回值：dp[m][n].

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        dp[0][0]=true;
        for(int i=2;i<=n;i+=2){
            if(p[i-1]=='*') dp[0][i]=true;
            else break;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p[j-1]=='*') dp[i][j]=((p[j-2]==s[i-1] || p[j-2]=='.') && dp[i-1][j]) || dp[i][j-2];
                else dp[i][j]=(p[j-1]=='.' || p[j-1]==s[i-1]) && dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};




//或者为下面的代码




class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        s=' '+s;
        p=' '+p;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        dp[0][0]=true;
        for(int i=2;i<=n;i+=2){
            if(p[i]=='*') dp[0][i]=true;
            else break;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p[j]=='*') dp[i][j]=((p[j-1]==s[i] || p[j-1]=='.') && dp[i-1][j]) || dp[i][j-2];
                else dp[i][j]=(p[j]=='.' || p[j]==s[i]) && dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};
交错字符串

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

为了便于表述，在s1,s2,s3每个字符串的最前边增加一个空格。

状态表示：dp[i][j]表示字符串s1[1,i]区间和字符串s2[1,j]区间能否凑成字符串s3的[1,i+j]区间。

状态转移方程：

初始化：

初始化第一行规则：依次判断字符串s2和s3对应位置是否相等，相等则为true，否则为false并break.

初始化第一列规则：依次判断字符串s1和s3对应位置是否相等，相等则为true，否则为false并break.

填表顺序：从上往下，从左往右。

返回值：dp[m][n]。

代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.size(),n=s2.size();
        if(m+n!=s3.size()) return false;
        s1=' '+s1;
        s2=' '+s2;
        s3=' '+s3;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        for(int i=0;i<=m;i++)
            if(s1[i]==s3[i]) dp[i][0]=true;
            else break;
        for(int i=0;i<=n;i++)
            if(s2[i]==s3[i]) dp[0][i]=true;
            else break;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=(s1[i]==s3[i+j] && dp[i-1][j]) || (s2[j]==s3[i+j] && dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};
两个字符串的最小ASCII删除和

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

题目中是求两个字符串的最小ASCII删除和，若直接求两个字符串的最小ASCII删除和有点麻烦，采用“正难则反”的思想，由于字符串时确定的，即两个字符串的ASCII值总和是确定的，那么只需要求出两个字符串的所有公共子序列中ASCII值最大的子序列，用sum-2*公共子序列ASCII最大值即可。

状态表示：dp[i][j]表示字符串s1[0,i]区间和字符串s2[0,j]区间所有的公共子序列中ASCII总和最大的值。

状态转移方程：

                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

                if(s1[i-1]==s2[j-1])

                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);

初始化：不用初始化。

填表顺序：从上往下，从左往右。

返回值：ret-2*dp[m][n]。

代码

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m=s1.size(),n=s2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        int ret=0;
        for(char ch:s1)
            ret+=ch;
        for(char ch:s2)
            ret+=ch;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                if(s1[i-1]==s2[j-1]) 
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);
            }
        }
        return ret-2*dp[m][n];
    }
};
最长重复子数组

题目

思路

根据经验+题目要求，我们将屡试不爽的采用“以某个位置”为结尾来分析问题。

如果以区间来分析问题，仔细分析一下会发现是错误的，因为子数组是连续的，而子序列可以连续也可以不连续，那么我们将以某个位置为结尾来分析问题。

状态表示：dp[i][j]表示数组nums1[0,i]和数组nums2[0,j]区间的所有重复子数组中的最长的长度。

状态转移方程：

初始化：不用初始化。

填表顺序；从上往下，从左往右。

返回值：dp表最大值。

代码

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

阅读全部

相关推荐

  6. 两个数组的交集

    2024-07-22 09:54:03       33 阅读

  8. 两个数组的交集

    2024-07-22 09:54:03       35 阅读

  10. 349. 两个数组的交集

    2024-07-22 09:54:03       17 阅读

最近更新

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

    2024-07-22 09:54:03       52 阅读

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

    2024-07-22 09:54:03       54 阅读

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

    2024-07-22 09:54:03       45 阅读

  19. Python语言-面向对象

    2024-07-22 09:54:03       55 阅读

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

    2024-07-22 09:54:03       50 阅读

热门阅读

  5. 【已解决】服务器无法联网与更换镜像源

    2024-07-22 09:54:03       19 阅读

  6. 网络编程：UDP数据报套接字编程与TCP流套接字编程

    2024-07-22 09:54:03       18 阅读

  10. 20240721图像扩边与填充详解

    2024-07-22 09:54:03       15 阅读

  13. 自动化UI测试元素定位精炼

    2024-07-22 09:54:03       16 阅读

  17. 贪吃蛇游戏

    2024-07-22 09:54:03       16 阅读

  24. 16、基于共享内存二叉树的LRU

    2024-07-22 09:54:03       14 阅读

  29. springboot集成kafka | 分布式消息发布和订阅系统

    2024-07-22 09:54:03       15 阅读