Hiểu bài toán

Cho hai xâu ký tự s và p chỉ chứa các ký tự Latinh thường. Đếm số cách xóa một số ký tự (có thể không xóa) từ s và p sao cho xâu kết quả nhận được từ s và xâu kết quả nhận được từ p đều khác rỗng và giống nhau. Hai cách xóa được coi là khác nhau nếu tập hợp các vị trí bị xóa ít nhất một xâu là khác nhau. Kết quả cần trả về modulo 1000000007.

Về bản chất, bài toán yêu cầu tính tổng số cách chọn một xâu con không rỗng chung của s và p. Với mỗi xâu con chung t, số cách tạo ra t từ s nhân với số cách tạo ra t từ p là số cách xóa tương ứng cho cặp xâu con đó. Do đó, tổng số cách xóa là: $$ \sum_{t \in C(s, p)} ( \text{số cách tạo } t \text{ từ } s ) \times ( \text{số cách tạo } t \text{ từ } p ) $$ Trong đó C(s, p) là tập hợp tất cả các xâu con chung không rỗng của s và p.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (Tính trực tiếp theo định nghĩa)

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 2005;

int dp[MAXN][MAXN]; // dp[i][j] là số cách xóa để tạo ra xâu con chung từ s[0..i-1] và p[0..j-1]

int main() {
    string s, p;
    cin >> s >> p;
    int n = s.size();
    int m = p.size();

    // Khởi tạo base case: Xâu con rỗng có 1 cách tạo (xóa hết)
    // Tuy nhiên, đề bài yêu cầu xâu khác rỗng.
    // Ta có thể tính dp[i][j] là tổng số cách cho các xâu con (kể cả rỗng)
    // Sau đó trừ đi 1 (cách tạo xâu rỗng).
    // Hoặc tập trung vào việc tạo xâu con không rỗng.

    // Công thức QHĐ:
    // Nếu s[i-1] == p[j-1]: 
    //    dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1
    //    (Lý giải: Các cách không dùng ký tự này (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1])
    //     + Các cách dùng ký tự này để đóng xâu mới hoặc nối vào xâu cũ)
    //    Thực chất công thức đúng là:
    //    dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1 (nếu s[i-1]==p[j-1])
    //    Tại sao là +1? Vì dp[i-1][j] không chứa cách tạo xâu kết thúc bằng s[i-1] từ p[0..j-1]
    //    dp[i][j-1] không chứa cách tạo xâu kết thúc bằng p[j-1] từ s[0..i-1]
    //    Ký tự s[i-1]==p[j-1] cho phép tạo thêm 1 xâu con mới (độ dài 1) và các xâu con mới bằng cách nối vào các xâu con kết thúc trước đó tại (i-1, j-1).
    //    Công thức chuẩn xác để tính t tổng số cách cho các xâu con chung:
    //    dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    //    if (s[i-1] == p[j-1]) dp[i][j] += dp[i-1][j-1] + 1
    //    Hay gọn hơn: if (s[i-1] == p[j-1]) dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1
    //                 else dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (s[i-1] == p[j-1]) {
                dp[i][j] = ((long long)dp[i-1][j] + dp[i][j-1] + 1) % MOD;
            } else {
                dp[i][j] = ((long long)dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
                if (dp[i][j] < 0) dp[i][j] += MOD;
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

• Time Complexity: O(N * M) với N, M là độ dài hai xâu (<= 2000)
• Space Complexity: O(N * M)

Đây là cách tiếp cận trực tiếp nhất dựa trên công thức quy hoạch động để tính tổng số cách tạo các xâu con chung.

dp[i][j] lưu tổng số cách tạo các xâu con chung từ tiền tố s[0...i-1] và p[0...j-1].

1. Trường hợp s[i-1] == p[j-1]: Ký tự mới giống nhau.

   • Các cách tạo xâu con không dùng ký tự này: dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1].
   • Các cách tạo xâu con có sử dụng ký tự này:
     • Tạo xâu con độ dài 1 (chính là ký tự này): 1 cách.
     • Nối ký tự này vào sau tất cả các xâu con chung của s[0...i-2] và p[0...j-2]: dp[i-1][j-1] cách.
   • Tổng: dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1.

2. Trường hợp s[i-1] != p[j-1]: Ký tự mới khác nhau.

   • Các cách tạo xâu con không dùng ít nhất một trong hai ký tự mới.
   • Sử dụng nguyên lý bù trừ tập hợp: dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1].

Độ phức tạp: O(N*M) thời gian và bộ nhớ, chấp nhận được với N, M <= 2000.

Cách Quy hoạch động tối ưu (Giảm bộ nhớ)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();

    // Chỉ cần lưu hàng trước và hàng hiện tại
    vector<long long> prev(m + 1, 0);
    vector<long long> curr(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        // Lưu lại diagonal value (dp[i-1][j-1]) trước khi cập nhật
        long long diag = 0;
        for (int j = 1; j <= m; j++) {
            long long temp = curr[j]; // Lưu giá trị curr[j] (tương lai là diagonal)

            if (A[i-1] == B[j-1]) {
                curr[j] = (prev[j] + curr[j-1] + 1) % MOD;
            } else {
                curr[j] = (prev[j] + curr[j-1] - prev[j-1]) % MOD;
                if (curr[j] < 0) curr[j] += MOD;
            }

            prev[j-1] = diag; // Cập nhật prev cho lần lặp sau
            diag = temp;       // Cập nhật diagonal cho lần lặp sau
        }
        prev[m] = curr[m]; // Cập nhật phần tử cuối cùng của prev
        // Hoặc đơn giản hơn, swap vector:
        // swap(prev, curr);
        // fill(curr.begin(), curr.end(), 0);
        // Nhưng cách dùng vector 1D và biến diagonal/tracking value này tốn O(1) bộ nhớ extra.

        // Cách dễ hiểu hơn:
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }

    cout << prev[m] << "\n";
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(M)

Bài toán này chỉ cần thông tin từ hàng i-1 và i để tính toán.

Chúng ta có thể tối ưu bộ nhớ từ O(N*M) xuống O(M) bằng cách sử dụng hai mảng dp và dp_prev (hoặc curr và prev).

Hàm chuyển trạng thái: curr[j] (tại hàng i) được tính dựa trên:

• prev[j] (hàng i-1, cột j)
• curr[j-1] (hàng i, cột j-1)
• prev[j-1] (hàng i-1, cột j-1)

Với mỗi hàng i mới:

1. Duyệt j từ 1 đến m.
2. Tính curr[j] theo công thức đã biết.
3. Sau khi tính xong hàng i, gán prev = curr và chuẩn bị tính hàng i+1.

Lưu ý: Trong vòng lặp j, nếu tính curr[j] rồi ghi đè trực tiếp, ta phải đảm bảo rằng prev[j-1] (giá trị cũ của hàng trước tại cột j-1) chưa bị ghi đè. Tuy nhiên, trong công thức curr[j] = prev[j] + curr[j-1] - prev[j-1], ta cần prev[j-1]. Nếu ta chỉ dùng 1 mảng dp và cập nhật theo chiều tăng của j, thì dp[j-1] đã được cập nhật cho hàng hiện tại. Vì vậy ta cần một mảng dp_prev lưu hàng trước đó.

Một cách khác là dùng 1 mảng dp và một biến temp để lưu giá trị dp[j-1] trước khi cập nhật, nhưng cách dùng 2 mảng prev và curr rõ ràng và dễ bảo trì hơn.

Cách Quy hoạch động (Dùng mảng 2 chiều)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % MOD;
            } else {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD;
                if (dp[i][j] < 0) dp[i][j] += MOD;
            }
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Đây là cách hiện thị trực quan nhất của thuật toán quy hoạch động.

Ta khai báo ma trận 2 chiều dp[n+1][m+1].

• dp[i][j] là kết quả cho xâu A độ dài i và xâu B độ dài j.

Logic tính toán như sau:

• Nếu A[i-1] == B[j-1]: Ký tự này có thể là ký tự cuối của xâu con chung. Các cách tạo xâu con chung bao gồm:
  • Các cách không dùng ký tự này của A (hoặc B): dp[i-1][j] + dp[i][j-1].
  • Tuy nhiên, dp[i-1][j] và dp[i][j-1] đều chứa các cách dùng ký tự A[i-1] (trong dp[i-1][j] là các cách dùng A[i-1] nhưng không dùng B[j-1]? Không, dp[i-1][j] dùng A[0..i-2] và B[0..j-1]. dp[i][j-1] dùng A[0..i-1] và B[0..j-2]).
  • Đúng hơn là: dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1.
  • Tại sao lại là +1? Vì dp[i-1][j] không tính trường hợp kết thúc bằng A[i-1] (vì A chỉ đến i-2). dp[i][j-1] không tính trường hợp kết thúc bằng B[j-1] (vì B chỉ đến j-2). Ký tự A[i-1] == B[j-1] cho phép tạo thêm 1 xâu con mới độ dài 1. Nó cũng cho phép nối vào sau tất cả các xâu con chung của A[0..i-2] và B[0..j-2]. Số lượng xâu con chung của A[0..i-2] và B[0..j-2] là dp[i-1][j-1]. Vậy tổng số cách mới là dp[i-1][j-1] + 1.
  • Do dp[i-1][j] + dp[i][j-1] đã bao gồm dp[i-1][j-1] 2 lần (theo nguyên lý bù trừ), ta có thể viết: dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) + (dp[i-1][j-1] + 1) = dp[i-1][j] + dp[i][j-1] + 1.

• Nếu A[i-1] != B[j-1]: Không thể dùng cả hai ký tự này làm ký tự cuối cùng của xâu con chung.
  • dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1].

Cách này dễ hiểu nhất nhưng tốn bộ nhớ O(N*M). Với N, M <= 2000, bộ nhớ ~32MB, hoàn toàn chấp nhận được.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về đếm tổng các cách tạo các xâu con chung không rỗng.
• Công thức QHĐ: dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1 nếu s[i-1]==p[j-1], ngược lại dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1].
• Có thể tối ưu bộ nhớ từ O(N*M) xuống O(M) bằng cách dùng mảng 1 chiều.

Lỗi thường gặp

• Xử lý số âm trong phép trừ khi lấy modulo.
• Hiểu sai ý nghĩa của các trường hợp trong công thức quy hoạch động dẫn đến bỏ sót cách tính hoặc tính trùng lặp.