【线性 dp】A005_LC_不同的子序列（记忆化 / dp 分类讨论）

一、Problem

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 1：
输入：S = "rabbbit", T = "rabbit"
输出：3
解释：

如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

二、Solution

方法一：记忆化

思路

问题本质是抽出 $s$ 中的几个子序列来组成 $t$，看有多少种方案；

• 边界
  • 如果 t 匹配完成，s 还没有遍历完，那说明在 s 中找到了几个合法的几个子序列来组成 t
  • 如果 s 匹配完成，t 还没有遍历完，那说明在 s 中找没有找到合法的几个子序列来组成 t
• 枚举
  • 因为是子序列，我们可能需要错开 s 的某一个字符，然后从新的字符开始继续匹配，故，我们需要枚举一个 $k ∈ [i, n)$
  • 如果 s[k] = t[j]，继续 s 和 t 都进行下一轮匹配

class Solution {
public:
    int n, m;
    vector<vector<int>> f;
	int dfs(int i, int j, string& s, string& t) {
		if (j == m) return 1;
		if (i == n) return 0;
		if (f[i][j]!=-1)return f[i][j];
		int c=0;
        for (int k = i; k < n; k++) if (s[k] == t[j]) {
            c+=dfs(k+1,j+1,s,t);
        }
        return f[i][j]=c;
	}
    int numDistinct(string s, string t) {
    	n=s.size(), m=t.size();
        f.resize(n, vector<int>(m, -1));
    	return dfs(0, 0, s, t);
    }
};

效率不高…

复杂度分析

• 时间复杂度：$O(n^2m)$，
• 空间复杂度：$O(nm)$，

---

方法二：dp

状态转移的情况不难想，最难的是如何转移：

• 定义状态：
  • $f[i][j]$ 表示用 s 的前 i 个字符匹配 t 的前 j 个字符的方案数
• 思考初始化：
  • $f[0][*] = 1$ 经验吧，无逻辑可言
• 思考状态转移方程：
  • $s[i] \not= t[j]$ 时，证明 $s[:i-1]$ 这一段不可能将 $t[:j]$ 匹配完的了， $f[i][j] = f[i-1][j]$
  • $s[i] = t[j]$ 时，有两种情况：
    • 如果 $s[:i-1]$ 中也有 $s[i]$ 的话，方案数应该等于之前不用 s[i] 也能将 t[:j] 匹配的方案数，故 f[i][j] += f[i-1][j]
    • 如果 $s[:i-1]$ 中没有 $s[i]$ 的话，那方案数是 f[i-1][j-1]，故 f[i][j] += f[i-1][j-1]
    • 综上：f[i][j] += f[i-1][j] + f[i-1][j-1]
• 思考输出：$f[n][m]$

class Solution {
public:
    int numDistinct(string s, string t) {
    	long n = s.size(), m = t.size(), f[n+1][m+1]; memset(f, 0, sizeof f);
        if (n < m) return 0;
        for (int i=0; i<=n; i++) f[i][0]=1;

        for (int i=1; i<=n; i++)
    	for (int j=1; j<=m; j++) {
    		if (s[i-1]==t[j-1]) f[i][j] = f[i-1][j] + f[i-1][j-1];
    		else 		        f[i][j] = f[i-1][j];
    	}
        return f[n][m];
    }
};

复杂度分析

• 时间复杂度：$O(nm)$，
• 空间复杂度：$O(nm)$，

本文地址：https://blog.csdn.net/qq_43539599/article/details/107605955