C ++中的不同子序列
假设我们有字符串S和T。我们必须计算等于T的S的不同序列数。
我们知道一个字符串的子序列是一个新字符串，它是通过删除一些字符（可以是无字符）而不会干扰其余字符的相对位置而从原始字符串形成的。（例如，“ACE”是“ABCDE”的子序列，而“AEC”则不是）。
如果输入字符串是“baalllloonnn”和“balloon”，那么将有36种不同的选择方式。
为了解决这个问题，我们将遵循以下步骤-
n：=s的大小，m：=t的大小。通过在空格之前连接s和t来更新它们
制作一个大小为（n+1）x（m+1）的矩阵
设置dp[0，0]：=1，然后为所有行的第0列设置1，放入1
对于我在1到n范围内
如果s[i]=t[j]，则
dp[i，j]：=dp[i，j]+dp[i–1，j]
dp[i，j]：=dp[i–1，j–1]
对于1到m范围内的j
返回dp[n，m]
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size();
int m = t.size();
s = " " + s;
t = " " + t;
vector < vector <lli>> dp(n + 1, vector <lli> (m + 1));
dp[0][0] = 1;
for(int i = 1; i<= n; i++)dp[i][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
dp[i][j]+= dp[i - 1][j];
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.numDistinct("baalllloonnn", "balloon"));
}输入值
"baalllloonnn" "balloon"
输出结果
36