问题
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
例子
S = "rabbbit", T = "rabbit"
Return 3.
分析
题目的意思是,通过删除字符,S有多少种方法可以变成T.
动态规划:
- 状态表
dp[i][j],表示S[0, i - 1]有dp[i][j]种方法可以变成T[0, j - 1] - 初始状态
dp[0][0] = 1 空字符串只有一种方法变成空字符串(不进行任何操作)
dp[i][0] = 1, i >= 1 字符串只有一种方法变成空字符串(删除所有字符)
dp[0][j] = 0, j >= 1 空字符串没法变成非空字符串 - 状态转移方程
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j], if S[i - 1] == T[j - 1]
dp[i][j] = dp[i - 1][j], if S[i - 1] != T[j - 1]
注:当S[i - 1] == T[j - 1]时,可以有两种变化方法可以选择:一种是删除S[i - 1],用S[0, i - 2]变成T[0, j - 1],有dp[i - 1][j]种方法;还有一种是保留S[i - 1],用S[0, i - 2]变成T[0, j - 2],有dp[i - 1][j - 1]种方法。当S[i - 1] != T[j - 1]时,只能删除S[i - 1]。
要点
dp
时间复杂度
O(mn)
空间复杂度
O(mn) or O(m) or O(n)
代码
Space Complexity O(mn)
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[0][0] = 1;
for (int i = 1; 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++) {
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[m][n];
}
};
Space Complexity O(n)
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= m; i++) {
int pre = dp[0];
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (s[i - 1] == t[j - 1])
dp[j] += pre;
pre = temp;
}
}
return dp[n];
}
};