当前位置： 移动技术网 > IT编程>开发语言>.net > 【线性 dp】A005_LC_不同的子序列（记忆化 / dp 分类讨论）

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

2020年07月28日  | 移动技术网IT编程  | 我要评论

一、Problem

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

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

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

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

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

二、Solution

方法一：记忆化

思路

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

  • 边界
    • 如果 t 匹配完成，s 还没有遍历完，那说明在 s 中找到了几个合法的几个子序列来组成 t
    • 如果 s 匹配完成，t 还没有遍历完，那说明在 s 中找没有找到合法的几个子序列来组成 t
  • 枚举
    • 因为是子序列，我们可能需要错开 s 的某一个字符，然后从新的字符开始继续匹配，故，我们需要枚举一个 k∈[i,n)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(n2m)O(n^2m)，
  • 空间复杂度：O(nm)O(nm)，

方法二：dp

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

  • 定义状态：
    • f[i][j]f[i][j] 表示用 s 的前 i 个字符匹配 t 的前 j 个字符的方案数
  • 思考初始化：
    • f[0][∗]=1f[0][*] = 1 经验吧，无逻辑可言
  • 思考状态转移方程：
    • s[i]≠t[j]s[i] \not= t[j] 时，证明 s[:i−1]s[:i-1] 这一段不可能将 t[:j]t[:j] 匹配完的了， f[i][j]=f[i−1][j]f[i][j] = f[i-1][j]
    • s[i]=t[j]s[i] = t[j] 时，有两种情况：
      • 如果 s[:i−1]s[:i-1] 中也有 s[i]s[i] 的话，方案数应该等于之前不用 s[i] 也能将 t[:j] 匹配的方案数，故 f[i][j] += f[i-1][j]
      • 如果 s[:i−1]s[:i-1] 中没有 s[i]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]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)，
  • 空间复杂度：O(nm)O(nm)，

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网