Distinct Subsequences: นับลำดับย่อยที่แตกต่างกันใน C++

ปัญหา

กำหนดสตริง S และ T ให้หาจำนวนลำดับย่อย (Subsequence) ของ S ที่เท่ากับ T โดยลำดับย่อยคือสตริงที่ได้จากการลบตัวอักษรบางส่วน (อาจไม่ลบ) จากสตริงต้นฉบับ โดยไม่เปลี่ยนลำดับสัมพัทธ์ของตัวอักษรที่เหลือ

ตัวอย่าง: S = "baalllloonnn", T = "balloon" → ผลลัพธ์ = 36 วิธี

แนวคิด Dynamic Programming

กำหนด dp[i][j] = จำนวนวิธีสร้าง T[0..j-1] จาก S[0..i-1]

Base Case

• dp[0][0] = 1 (สตริงว่างจากสตริงว่าง มี 1 วิธี)
• dp[i][0] = 1 สำหทุก i (สตริงว่าง T จาก S ใดๆ มี 1 วิธี คือลบทั้งหมด)

Recurrence

สำหรับ i = 1..n, j = 1..m:

if S[i-1] == T[j-1]:
    dp[i][j] = dp[i-1][j-1]  // ใช้ตัวอักษรนี้จับคู่
dp[i][j] += dp[i-1][j]       // ไม่ใช้ตัวอักษรนี้ (ข้ามไป)

โค้ด C++

#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;  // 1-based indexing
        t = " " + t;
        
        vector<vector<lli>> dp(n + 1, vector<lli>(m + 1, 0));
        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];
    }
};

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

การเพิ่มประสิทธิภาพ Space (Optional)

สามารถลด Space เหลือ O(m) ได้โดยใช้ 1D DP Array และอัปเดตจากขวาไปซ้าย:

vector<lli> dp(m + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {
        if (s[i-1] == t[j-1]) {
            dp[j] += dp[j-1];
        }
    }
}
return dp[m];

Input / Output

Input:  "baalllloonnn" "balloon"
Output: 36

ความซับซ้อน

• Time: O(n × m)
• Space: O(n × m) หรือ O(m) แบบเพิ่มประสิทธิภาพ