数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究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
i 的范围从 1 到 n
j 的范围从 1 到 m
如果 s[i] = t[j]，那么
dp[i, j] := dp[i – 1, j – 1]
dp[i, j] := dp[i, j] + dp[i – 1, 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
更新时间：26-May-2020
139 人查看
广告