Palindrome Partitioning - หาจำนวนการตัดน้อยที่สุดให้เป็นพาลินโดรมใน C++

ภาพรวมปัญหา

มีสตริง ต้องหาจำนวนการตัด (cuts) น้อยที่สุด เพื่อให้ทุกส่วนเป็นพาลินโดรม

ตัวอย่าง: "ababbbabbababa" → 3 cuts (a | babbbab | b | ababa)

อัลกอริทึม (Dynamic Programming)

1. n = ความยาวสตริง
2. สร้างตาราง cut[n][n] และ pal[n][n] (pal[i][j] = true ถ้า s[i..j] เป็นพาลินโดรม)
3. ฐาน: pal[i][i] = true, cut[i][i] = 0
4. สำหรับความยาว 2 ถึง n:
   • ตรวจสอบ pal[i][j]
   • ถ้าเป็นพาลินโดรม: cut[i][j] = 0
   • ไม่ใช่: cut[i][j] = min(cut[i][k] + cut[k+1][j] + 1) สำหรับ k = i ถึง j-1
5. return cut[0][n-1]

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

#include <iostream>
#include <climits>
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 << "Min cuts for Palindrome Partitioning is: " << minPalPartion(str);
}

Input / Output

Input:  ababbbabbababa
Output: Min cuts for Palindrome Partitioning is: 3