动态规划＜九＞两个数组的dp

目录

引例

 LeetCode经典OJ题

1.第一题

2.第二题

 3.第三题

 4.第四题

 5.第五题

 6.第六题

 7.第七题

引例

OJ传送门LeetCode<1143>最长公共子序列

画图分析：

使用动态规划解决

1.状态表示 ------经验+题目要求

经验为选取第一个字符串的[0,i]区间以及第二个字符串的[0,j]区间作为研究对象，再根据实际的题目要求，确定状态表示

dp[i][j]表示：字符串s1的[0,i]区间以及字符串s2的[0,j]区间内的所有子序列中，最长公共子序列的长度

2.状态转移方程----根据最后一个位置的状况，分情况讨论

3.初始化

在关于字符串的dp问题中，空串也是有研究意义的

在这里引入空串是为了方便我们后面的初始化，根据状态转移方程会发生越界的为第一行和第一列，因此可以采用多加一行和一列的方式来完成初始化

注意下标的映射关系

4.填表顺序   从上往下，从左往右

5.返回值 dp[m][n](m,n分别为字符串的长度)

具体代码：

int longestCommonSubsequence(string s1, string s2) 
    {
        int m=s1.size(),n=s2.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(s1[i-1]==s2[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];
    }

 LeetCode经典OJ题

1.第一题

OJ传送门LeetCode<1035>不相交的线

画图分析：

 动态规划各步与引例相同

具体代码：

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];
    }

2.第二题

OJ传送门LeetCode<115>不同的子序列

画图分析：

 使用动态规划解决

1.状态表示

dp[i][j]表示:字符串s的[0,j]区间内所有的子序列中，有多少个字符串t的[0,i]区间内的子串

2.状态转移方程

根据字符串s的子序列的最后一个位置包不包含s[j]

3.初始化

会发生越界的为第一行和第一列，可以采用多加一行和一列的方式来初始化

根据状态表示，i=0的这一行是去s中寻找空串，有一个，j=0的这一列是空串中寻找t的子串，是找不到的，初始化为0

4.填表顺序

从上往下，从左往右

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

具体代码：

int numDistinct(string s, string t) 
    {
        const int MOD=1e9+7;
        int m=t.size(),n=s.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=0;i<=n;++i) dp[0][i]=1;//初始化
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
            {
                dp[i][j]+=dp[i][j-1];
                if(t[i-1]==s[j-1])
                {
                    dp[i][j]+=dp[i-1][j-1];
                    dp[i][j]%=MOD;
                }
            }
        return dp[m][n];
    }

 3.第三题

OJ传送门LeetCode<44>通配符匹配

画图分析：

使用动态规划解决

1.状态表示

dp[i][j]表示:p[0,j]区间内的子串能否匹配s[0,i]区间内的子串

2.状态转移方程 --根据最后一个位置的状况来划分问题

3.初始化  初始化第一行和第一列

第一行i=0时，s是空串，当j不断增大时，当第一次遇到不是*的就会匹配不成功，为false

第一列j=0时，p是空串，去匹配p的话，就会匹配不成功，为false

4.填表顺序   从上往下，从左往右

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

具体代码：

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=1;i<=n;++i) 
        {
            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]=dp[i][j-1] || dp[i-1][j];
                else
                    dp[i][j]=(p[j]=='?' || s[i]==p[j])&& dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }

 4.第四题

OJ传送门LeetCode<10>正则表达式匹配

画图分析：

使用动态规划解决

1.状态表示

dp[i][j]表示p[0,j]区间内的子串是否能匹配s[0,i]区间内的子串

2.状态转移方程------根据最后一个位置的状态，分情况讨论

3.初始化

初始化第一行和第一列

当i=0,s为空串,p必须保持偶数位为*,当第一次没有遇到*时，就初始化为false

当j=0,p为空串，去匹配s的话，都是不成功的，初始化为false

4.填表顺序

从上往下，从左往右

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

具体代码：

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 j=2;j<=n;j+=2)
            if(p[j]=='*') dp[0][j]=true;
            else break;
        
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(p[j]=='*')
                    dp[i][j]=dp[i][j-2] || (p[j-1]=='.' || p[j-1]==s[i]) && dp[i-1][j];
                else
                    dp[i][j]=(p[j]==s[i] || p[j]=='.') && dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }

 5.第五题

OJ传送门LeetCode<97>交错字符串

画图分析：

 使用动态规划解决

可以做个预处理，每个字符串添加一个空白字符

1.状态表示

dp[i][j]表示s1[1,i]区间内的字符串以及s2[1,j]区间内的字符串，能否拼接成s3[1,i+j]区间内的字符串

2.状态转移方程

3.初始化    初始化第一行和第一列

i=0即s1为空串，字符串s2与s3逐个往后匹配，当第一次遇到不匹配时，初始化为false

j=0即s2为空串，与上面一样

4.填表顺序    从上往下，从左往右

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

具体代码：

 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));
        dp[0][0]=true;
        for(int i=1;i<=n;++i)//初始化第一行
            if(s2[i]==s3[i]) dp[0][i]=true;
            else break;
        for(int i=1;i<=m;++i)//初始化第一列
            if(s1[i]==s3[i]) dp[i][0]=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];
    }

 6.第六题

OJ传送门LeetCode<712>两个字符串的最小ASCII码删除和

画图分析：

 会发现当两个字符串删除完之后剩下的为公共子序列，而公共子序列有很多，根据题意，我们只需求出两个字符串里面所有的公共子序列中，ASCII码的最大和，即可满足最小删除和

使用动态规划解决

1.状态表示

dp[i][j]表示s1[0,i]区间以及s2[0,j]区间内的所有子序列中，公共子序列的ASCII最大和

2.状态转移方程

3.初始化

不管是i=0,还是j=0,公共子序列都是空串，ASCII为0，即初始化为0

4.填表顺序    从上往下，从左往右

5.返回值       求出两个字符串的和sum,再减去2*dp[m][n]

具体代码：

int minimumDeleteSum(string s1, string s2) 
    {
        int m=s1.size(),n=s2.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)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(s1[i-1]==s2[j-1])
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);
            }
        
        int sum=0;
        for(auto x:s1) sum+=x;
        for(auto x:s2) sum+=x;
        return sum-2*dp[m][n];
    }

 7.第七题

OJ传送门LeetCode<718>最长重复子数组

画图分析：

 对于本道题若继续采用以往的经验的话，因为求取的是连续的子数组，必须保证能跟在前面位置的后面，因此不能采用

1.状态表示

dp[i][j]表示：nums1中以i位置元素为结尾的所有子数组以及nums2中以j位置元素为结尾的所有子数组中，最长重复子数组的长度

2.状态转移方程

3.初始化

初始化第一行和第一列为0

4.填表顺序   从上往下填每一行

5.返回值    dp表中的最大值

具体代码：

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;
    }