Distinct Subsequences trong C++

Cho chuỗi S và T, đếm số dãy con phân biệt của S bằng T. Dãy con: xóa bớt ký tự không đổi thứ tự tương đối.

Ví dụ: S="baalllloonnn", T="balloon" → 36 cách.

Giải thuật (Dynamic Programming)

DP[i][j] = số cách tạo T[0..j-1] từ S[0..i-1].

• DP[0][0] = 1, DP[i][0] = 1 (chuỗi rỗng).
• Nếu S[i-1] == T[j-1]: DP[i][j] = DP[i-1][j-1] + DP[i-1][j].
• Ngược lại: DP[i][j] = DP[i-1][j].

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        s = " " + s; t = " " + t; // 1-indexed
        vector<vector<lli>> dp(n + 1, vector<lli>(m + 1, 0));
        for (int i = 0; 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];
    }
};

int main() {
    Solution ob;
    cout << ob.numDistinct("baalllloonnn", "balloon"); // 36
    return 0;
}

Đầu vào / Đầu ra

Input: "baalllloonnn", "balloon"
Output: 36