LeetCode 392判断子序列 115不同的子序列 | 代码随想录25期训练营day55

动态规划算法12

LeetCode 392 判断子序列 2023.12.18

• 题目链接
• 代码随想录讲解[链接]
  

bool isSubsequence(string s, string t) {
    //此题与1143最长公共子序列、1035不想交的线基本相同，不同点在于此题只判断s是否为t的子序列，s.size()<=t.size()
    //1确定dp二维数组，dp[i][j]表示以s[i-1]、t[j-1]结尾相同的公共子序列的最大长度
    vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
    //3初始化，第一行和第一列必须初始化，意义上为0，因为遍历开始从s[0]与t[0]比较
    //2确定递推公式，4确定遍历顺序
    //顺序遍历
    for (int i = 1; i <= s.size(); i++)
    {
        for (int j = 1; j <= t.size(); j++)
        {
            //如果s[i-1]、t[j-1]相同,那么dp[i-1][j-1]+1
            if(s[i-1] == t[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                //如果s[i-1]、t[j-1]不相同,
                //那么dp[i][j]=s[0, i]与t[0, j-1]的公共序列最大长度
                dp[i][j] = dp[i][j-1];
            //与1143、1035的不同点，本题只判断s是否为t的子序列，考虑删除t中元素
            //dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    //最后判断最长公共子序列长度是否为s字符串的长度
    //如果是，则说明s是t的子序列
    //不相等，则说明不是
    if(dp[s.size()][t.size()] == s.size())
        return true;
    else
        return false;
}

LeetCode 115 不同的子序列 2023.12.18

• 题目链接
• 代码随想录讲解[链接]
  

int numDistinct(string s, string t) {
    //1确定dp二维数组，dp[i][j]表示以s[0, i-1]中有t[0, j-1]的出现个数
    vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1, 0));
    //3初始化，从递推公式中得出第一行和第一列必须初始化，空字符中t字符出现次数dp[0][i]为0
    //s字符中空字符出现次数dp[i][0]为1
    //2确定递推公式，4确定遍历顺序
    //顺序遍历
    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++)
        {
            //如果s[i-1]、t[j-1]相同,那么dp[i][j]=s[0, i-2]中有t[0, j-2]的个数+s[0,i-2]中有t[0,j-1]的个数
            if(s[i-1] == t[j-1])
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            //如果s[i-1]、t[j-1]不同，那么dp[i][j]=s[0,i-2]中有t[0,j-1]的个数
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    //最后返回s中有t的个数
    return dp[s.size()][t.size()];
}