[C国演义] 第二十二章

第二十二章

不同的子序列
交错字符串

不同的子序列

力扣链接

两个数组的dp问题 (子序列 && 子数组(子串)) ⇒ 分区间来讨论 ⇒ dp[i][j] -- 在s数组的[0, i]区间内, 去寻找t数组在[0, j]这段子串的个数
状态转移方程
遍历顺序
初始化
需要使用左上角的情况 ⇒ dp表可以多开一行, 多开一列
但是dp表中使用原 nums1 和 nums2的情况就会出现偏差, 解决方法
1. 访问nums1 和 nums2里面的情况, 就要 －1
2. 可以在nums1, nums2前面添加一个 空格 ⇒ 使得dp表中的下标和 nums1 和 nums2中的下标一致化

返回结果 – 返回dp[m][n]

class Solution {
public:
    int numDistinct(string s, string t) 
    {
        int m = s.size();
        int 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 j = 1; j <= n; j++)  dp[0][j] = 0;

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1;  j <= n;  j++)
            {
                // 情况1 -- 需要最后一个位置相等
                if(s[i-1] == t[j-1])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                // 情况2 -- 不需要任何条件
                dp[i][j] += dp[i-1][j];
            }
        }

        // 返回结果
        return dp[m][n];
    }
};

交错字符串

力扣链接

两个数组的dp问题 ⇒ dp[i][j] -- s1数组的 [0, i]区间内的字符串和 s2数组的 [0, j]区间内的字符串能否构成 s3数组中的 [0, i+j+1]这段区间的字符串

优化 -- s1, s2, s3前面都加一个空格 ⇒ s1中的[1, i]区间内的字符串和 s2中的[1, j]区间内的字符串能否构成 s3中[1, i+j]区间内的字符串
状态转移方程
遍历顺序
初始化
返回结果 – 返回 dp[m][n]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        int m = s1.size();
        int n = s2.size();
        int t = s3.size();

        // 大小不统一, 就直接返回false
        if(m+n != t)  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 <= m; i++)
        {
            if(s1[i] == s3[i])  dp[i][0] = true;
            else break;
        }
        for(int j = 1; j <= n; j++)
        {
            if(s2[j] == s3[j])  dp[0][j] = true;
            else  break;
        }

        // 填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                // 有一种情况满足就为true
                dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j] == true)
                || (s2[j] == s3[i+j] &&  dp[i][j-1] == true);
            }
        }

        // 返回结果
        return dp[m][n];
    }
};