UVa 10069 Distinct Subsequences：DP + 大整數計數子序列

題目大意

給字符串 A (長 n ≤ 10000) 和 B (長 m ≤ 100)，求 A 中有多少個**子序列**（不必連續）等於 B。答案可能極大，需大整數輸出。多測試案例。

動態規劃

dp[i][j] = A 前 j 字符中，出現 B 前 i 字符作為子序列的次數。
轉移：
- 不用 A[j]：dp[i][j] = dp[i][j-1]
- 用 A[j]（若 A[j-1] == B[i-1]）：dp[i][j] += dp[i-1][j-1]
初始：dp[0][j] = 1（空串是任意串子序列，1 種），dp[i][0] = 0 (i>0)。
答案：dp[m][n]。

空間優化

只需兩行滾動數組，或一維逆序更新。但因需大整數，Java `BigInteger` 直接用二維數組最簡單。

Java 完整代碼

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while (T-- > 0) {
            String A = cin.next();
            String B = cin.next();
            int n = A.length(), m = B.length();
            BigInteger[][] dp = new BigInteger[m+1][n+1];
            for (int j = 0; j <= n; ++j) dp[0][j] = BigInteger.ONE;
            for (int i = 1; i <= m; ++i) {
                dp[i][0] = BigInteger.ZERO;
                for (int j = 1; j <= n; ++j) {
                    dp[i][j] = dp[i][j-1];
                    if (A.charAt(j-1) == B.charAt(i-1))
                        dp[i][j] = dp[i][j].add(dp[i-1][j-1]);
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}

C++ 大整數替代

C++ 無內置大整數，可用數組模擬高精度加法，或引入 `boost::multiprecision::cpp_int`。

複雜度

• 時間：O(m × n) = 100 × 10000 = 10⁶ 狀態，每狀態大整數加法 O(位數) ≈ 幾十位，總計極快。
• 空間：O(m × n) 大整數對象，Java GC 自動管理。

總結

UVa 10069 是經典的「不同子序列計數」DP 題。關鍵點：
1. 狀態定義清晰：`dp[i][j]` 含義明確。
2. 大整數處理：Java `BigInteger` 一行解決；C++ 需手寫或用庫。
3. 空間可優化至 O(n)，但 m=100 很小，二維更清晰。