C++ 编程中的不同子序列
c++server side programmingprogramming
假设我们有字符串 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
for i in range 1 to n
for j in range 1 to m
if s[i] = t[j], then
dp[i, j] := dp[i – 1, j – 1]
dp[i, j] := dp[i, j] + dp[i – 1, j]
return 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
