Số bước tối thiểu xóa chuỗi sau khi lặp xóa chuỗi con palindrome trong C++

Đề bài

Cho một chuỗi chỉ chứa ký tự số nguyên. Cần xóa tất cả ký tự của chuỗi này trong số bước tối thiểu, trong đó mỗi bước có thể xóa chuỗi con là palindrome. Sau khi xóa chuỗi con, các phần còn lại được nối lại.

Ví dụ

Nếu chuỗi đầu vào là 3441213 thì cần tối thiểu 2 bước

• Đầu tiên xóa 121 khỏi chuỗi. Chuỗi còn lại là 3443
• Xóa chuỗi còn lại vì nó là palindrome

Thuật toán

Có thể dùng quy hoạch động để giải bài toán này

1. dp[i][j] biểu thị số bước xóa chuỗi con s[i, j]
2. Mỗi ký tự sẽ bị xóa riêng lẻ hoặc như một phần của chuỗi con. Trong trường hợp đầu tiên, xóa chính ký tự đó và gọi bài toán con (i+1, j)
3. Trong trường hợp thứ hai, duyệt qua tất cả vị trí xuất hiện của ký tự hiện tại ở bên phải. Nếu K là chỉ số của một vị trí đó, bài toán quy về hai bài toán con (i+1, K-1) và (K+1, j)
4. Có thể đạt bài toán con (i+1, K-1) vì ta có thể xóa cùng ký tự và gọi cho chuỗi con giữa
5. Cần xử lý trường hợp hai ký tự đầu tiên giống nhau, khi đó có thể quy trực tiếp về bài toán con (i+2, j)

Ví dụ mã C++

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

int getMinRequiredSteps(string str) {
    int n = str.length();
    int dp[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    for (int len = 1; len <= n; len++) {
        for (int i = 0, j = len - 1; j < n; i++, j++) {
            if (len == 1)
                dp[i][j] = 1;
            else {
                dp[i][j] = 1 + dp[i + 1][j];
                if (str[i] == str[i + 1]) {
                    dp[i][j] = min(1 + dp[i + 2][j], dp[i][j]);
                }
                for (int K = i + 2; K <= j; K++) {
                    if (str[i] == str[K]) {
                        dp[i][j] = min(dp[i + 1][K - 1] + dp[K + 1][j], dp[i][j]);
                    }
                }
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    string str = "3441213";
    cout << "Số bước tối thiểu cần: " << getMinRequiredSteps(str) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số bước tối thiểu cần: 2