นับจำนวน subsequence ที่เท่ากับ target ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะนับจำนวน subsequence ของ s ที่เท่ากับ t โดย s และ t เป็นสตริงตัวพิมพ์เล็ก ผลลัพธ์ mod 10⁹+7

ตัวอย่าง

Input: s = "abbd", t = "bd"
Output: 2
Subsequences: s[1]+s[3]="bd", s[2]+s[3]="bd"

อัลกอริทึม: Dynamic Programming

ให้ dp[j] = จำนวนวิธีสร้าง prefix t[0..j-1] จาก prefix ของ s ที่ประมวลผลแล้ว
เริ่มต้น dp[0] = 1 (empty string)
สำหรับแต่ละตัวอักษรใน s: อัปเดต dp จากท้ายไปหน้า

ตัวอย่างโค้ด

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

int solve(string s, string t) {
    const int MOD = 1000000007;
    if (t.empty()) return 0;
    if (t == s) return 1;
    if (t.size() > s.size()) return 0;
    
    vector dp(t.size() + 1, 0);
    dp[0] = 1;
    
    for (int i = 0; i < s.size(); i++) {
        vector old = dp;  // copy สำหรับอ้างอิงค่าเก่า
        for (int j = 0; j < t.size(); j++) {
            if (s[i] == t[j]) {
                dp[j + 1] = (dp[j + 1] + old[j]) % MOD;
            }
        }
    }
    
    return dp[t.size()] % MOD;
}

int main() {
    string s = "abbd", t = "bd";
    cout << solve(s, t);
    return 0;
}

ผลลัพธ์

2

การปรับปรุงพื้นที่ (Space Optimization)

ไม่ต้อง copy array ทุกครั้ง ให้วน j จากท้ายไปหน้า:

for (int i = 0; i < s.size(); i++) {
    for (int j = t.size() - 1; j >= 0; j--) {
        if (s[i] == t[j]) {
            dp[j + 1] = (dp[j + 1] + dp[j]) % MOD;
        }
    }
}

ความซับซ้อน

• เวลา: O(|s| × |t|)
• พื้นที่: O(|t|)

สรุป

DP นับ subsequence เท่ากับ target คลาสสิก (LeetCode 115 Distinct Subsequences) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ