Phân Chia Palindrome (Palindrome Partitioning)

Giới thiệu

Cho một chuỗi, phân chia chuỗi thành các chuỗi con sao cho mỗi chuỗi con là một palindrome. Mục tiêu là tìm số lần cắt nhỏ nhất để đạt được điều này.

Đầu vào và Đầu ra

Đầu vào: Chuỗi "ababbbabbababa"
Đầu ra: Số cắt tối thiểu = 3. Các palindrome: a | babbbab | b | ababa

Thuật toán Quy hoạch động

Sử dụng hai bảng: pal[i][j] cho biết chuỗi con i..j có phải palindrome không, và cut[i][j] lưu số cắt tối thiểu cho chuỗi con i..j.

minPalPart(str)
Begin
    n := độ dài str
    định nghĩa ma trận cut và pal kích thước n x n
    for i := 0 to n-1 do
        pal[i][i] := true; cut[i][i] := 0
    done
    for len := 2 to n do
        for i := 0 to n - len do
            j := i + len - 1
            if len = 2 then
                pal[i][j] := (str[i] = str[j])
            else
                pal[i][j] := (str[i] = str[j]) AND pal[i+1][j-1]
            if pal[i][j] then cut[i][j] := 0
            else
                cut[i][j] := ∞
                for k := i to j-1 do
                    cut[i][j] := min(cut[i][j], cut[i][k] + cut[k+1][j] + 1)
                done
        done
    done
    return cut[0][n-1]
End

Ví dụ C++

#include <iostream>
using namespace std;

int min(int a, int b) { return (a < b) ? a : b; }

int minPalPartion(string str) {
    int n = str.size();
    int cut[n][n];
    bool pal[n][n];
    for (int i = 0; i < n; i++) {
        pal[i][i] = true;
        cut[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (len == 2)
                pal[i][j] = (str[i] == str[j]);
            else
                pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];
            if (pal[i][j])
                cut[i][j] = 0;
            else {
                cut[i][j] = INT_MAX;
                for (int k = i; k <= j-1; k++)
                    cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j] + 1);
            }
        }
    }
    return cut[0][n-1];
}

int main() {
    string str = "ababbbabbababa";
    cout << "Số cắt tối thiểu cho phân chia palindrome: " << minPalPartion(str);
    return 0;
}

Kết quả

Số cắt tối thiểu cho phân chia palindrome: 3