資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
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
對於 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
更新於:09-6 月-2020
246 次瀏覽
廣告