动态规划经典模型：双数组问题的通用解决框架与实战

class Solution

{

public:

    int longestCommonSubsequence(string s1, string s2)

    {

        int m=s1.size();

        int n=s2.size();

  

        vector<vector<int>>dp(m+1,vector<int>(n+1));//规格是(m+1,n+1)的矩阵，初始化的话里面默认是0

  

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                //两个结尾的字符是相同的，那么我们去[i-1][j-1]这个区间去找最长的子序列

                if(s1[i-1]==s2[j-1])//因为我们阔了一行和一列，所以我们是需要进行-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 s1, string s2)

    {

        int m=s1.size();

        int n=s2.size();

        s1=" "+s1,s2=" "+s2;

        vector<vector<int>>dp(m+1,vector<int>(n+1));//规格是(m+1,n+1)的矩阵，初始化的话里面默认是0

  

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                //两个结尾的字符是相同的，那么我们去[i-1][j-1]这个区间去找最长的子序列

                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]);//两种情况的最大值

            }

  

        }

        return 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));//将这个矩阵初始化为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;

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

            }

        }

        return dp[m][n];

    }

};

class Solution

{

public:

    int numDistinct(string s, string t)

    {

        int m=t.size(),n=s.size();

        vector<vector<double>>dp(m+1,vector<double>(n+1));

        for(int j=0;j<=n;j++)dp[0][j]=1;//将第一行初始化为1

  

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                //我们要考虑不使用 s 的第 j 个字符（即 s[j - 1]）来进行匹配的情况。

                dp[i][j]+=dp[i][j-1];//不包含s[j]的情况

                if(s[j-1]==t[i-1])dp[i][j]+=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;//保证dp数组下标和原始数组下标进行一个对应的操作

        vector<vector<bool>>dp(m+1,vector<bool>(n+1));//初始化默认是false

  

        //初始化操作

        dp[0][0]=true;//空字符串和空模式是匹配的。这个是基础的边界情况。

        for(int j=1;j<=n;j++)//字符串和模式的匹配情况，只有*才能匹配空字符串，如果不是空字符串的话，那么匹配的结果就是false

            if(p[j]=='*')dp[0][j]=true;//当这个位置是*的时候，我们第一行初始化为true

            else break;//如果碰到的不是*的话，那么我们直接退出，默认初始化为false

        //填表

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                if(p[j]=='*')

                {

                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                    //如果 dp[i-1][j] 为 true，意味着 * 匹配了一个字符；
                    //如果 dp[i][j-1] 为 true，意味着 * 匹配了零个字符。

                }

                else //剩下的两种情况

                {

                    //如果这个最后一个符号是问号或者最后的两个字符串最后一个字符都是相等的

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

                    //只要这两种情况有一种成立的话，并且加上后面的dp[i-1][j-1]==true这个条件的话,如果都成立的话

                    //dp[i][j]就等于true

  

                    //这个代码就是将p[j]是普通字符和p[j]='?'的情况都进行了一个包括的操作

                }

            }

        }

        return dp[m][n];

    }

};

class Solution

{

public:

    bool isMatch(string s, string p)

    {

        int m=s.size(),n=p.size();

        s=" "+s,p=" "+p;

        //默认初始化为false

        vector<vector<bool>>dp(m+1,vector<bool>(n+1));//规模是(m+1,n+1)

  

        //初始化操作

        dp[0][0]=true;

        //因为此时我们是需要初始化第一行的，dp[0][j]，就是说s是空的，但是p不是空的，所以我们是需要堆p进行判断操作

        for(int j=2;j<=n;j+=2)//每次往后面移动两位，看看偶数位上是否为*

            if(p[j]=='*')dp[0][j]=true;//只要偶数位置上是*的话，那么我们就可以和前面一个位置上的字符与s这个空字符串进行匹配的操作了

            else break;//不是*的话直接跳出去，因为其他的都是false了

  

        //填表

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                if(p[j]=='*')

                {

                    //j位置是*的话，dp[i][j-2]就是一个字符和*然后匹配到s的空字符

                    //或者前面的字符是'.'或者j-1位置和i位置的字符相等，那么我们就匹配一个并且保留*，然后检查dp[i-1][j]是否为true就行了

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

                }

                else//就是这个位置上是普通字符和 '.'的两种情况

                {

                    //如果i和j位置的字符相等，或者是j位置的是'.' ,就是最后一个字符能匹配的情况下，那么我们就得看下dp[i-1][j-1]的位置了

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

                }

            }

        }

        return 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));

  

        dp[0][0]=true;//第一个位置，两个串都是空串的情况下

        //遍历第一行.s1是空的，但是s2不是空的，我们需要判断此时的s2是否等于s3了

        for(int j=1;j<=n;j++)

        {

            if(s2[j]==s3[j])dp[0][j]=true;

            else break;//如果字符不相等的话，我们直接break,剩下的都是false就行了

        }

  

        //初始化第一列,此时的s2是空的，那么我们就需要判断s1是否和s3对应元素相等了

        for(int i=1;i<=m;i++)

        {

            if(s1[i]==s3[i])dp[i][0]=true;

            else break;//如果字符不相等的话，我们直接break,剩下的都是false就行了

        }

  

        //开始进行填表

        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]==true)//这个就是s1的i位置元素等于s3的i+j的位置，并且dp[i-1][j]还是true

                        ||(s2[j]==s3[i+j]&&dp[i][j-1]==true);

            }

        }

        return 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));//初始化的话都是初始化为0就行了

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                //这两种情况就是这个公共子序列要么就是有s1[i]，没有s2[j]，要么就是没有s1[i]，有s2[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]);//我们这里加个s1[i]就行了，因为s2[j]==s1[i]。并且我们这里的s1[i-1]这里的-1就是为了找到原数组的字符元素

            }

        }

        //返回之前我们需要先统计两个字符串的ASCII

        int sum=0;

        //计算两个字符串的ASCII总和

        for(auto s:s1)sum+=s;

        for(auto s:s2)sum+=s;

        //减去公共子序列的ASCII，就可以得到我们的删除字符的 ASCII 值的最小和了。

        return sum-dp[m][n]-dp[m][n];//因为这个ASCII是从原来的两个字符串中剥离了n个两个相同的字符的，所以我们这里是需要乘以二的

    }

};

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));//都初始化为0就行了

        int ret=0;

        for(int i=1;i<=m;i++)

        {

            for(int j=1;j<=n;j++)

            {

                //如果nums1[i]!=nums2[j]的话，那么dp[i][j]=0,我们是不需要管的

                //下面是两个位置的元素相等，这里我们-1了，因为我们多加了一行和一列，所以需要进行-1映射坐标了

                if(nums1[i-1]==nums2[j-1])

                {

                    dp[i][j]=dp[i-1][j-1]+1;//加上当前的位置的长度

                    ret=max(ret,dp[i][j]);

                }

            }

        }

        return ret;

    }

};