算法随想Day48【动态规划】| LC392. 判断子序列、LC115-不同的子序列

LC392. 判断子序列

• 简单题学方法，困难题用方法

bool isSubsequence(string s, string t)
{
    int size_s = s.size();
    int size_t = t.size();
    vector<vector<int>> dp(size_s + 1, vector<int>(size_t + 1, 0));
    for (int i = 1; i <= size_s; ++i)
    {
        for (int j = 1; j <= size_t; ++j)
        {
            if (s[i - 1] == t[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[size_s][size_t] == size_s;
}

LC115. 不同的子序列

基于前面那么多题目的总结和推导，独立想出了一道Hard题的思路：

• dp[i] [j]含义：s[0] ~ s[j - 1]子序列 能够凑成 t[0] ~ t[i - 1]子序列 的方法数

• 由上图的推导所示，从主循环的第二行开始，一旦遇到与当前元素一致的，其dp值是由其 正左方 和 左上角 叠加所得的。其左方值代表，其之前已经满足能够凑成 t[0] ~ t[i - 1]子序列的方法数，其左上角值代表，其上一层能够凑成 t[0] ~ t[i - 2]子序列的方法数。

• 举个例子，对 a 行的第4个"1"，代表在s的子序列"babgb"中，暂时能找到"1"中方法凑成'"ba"，而下一个"4"，是由上层的“3”个"b"，加上这次的"a"，能凑成"3"种"ba"的方法，加上前面的"1"次，即为4次。

int numDistinct(string s, string t)
{
    int size_s = s.size();
    int size_t = t.size();
    vector<vector<uint64_t>> dp(size_t + 1, vector<uint64_t>(size_s + 1, 0));
    for (int j = 1; j <= size_s; ++j)
    {
        if (t[0] == s[j - 1])
        {
            dp[1][j] = dp[1][j - 1] + 1;
        }
        else
            dp[1][j] = dp[1][j - 1];
    }
    for (int i = 2; i <= size_t; ++i)
    {
        for (int j = 1; j <= size_s; ++j)
        {
            if (t[i - 1] == s[j - 1])
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
            }
            else
                dp[i][j] = dp[i][j - 1];
        }
    }
    return dp[size_t][size_s];
}