資料結構
網路
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 人檢視
廣告