การแบ่งสตริงเป็นพาลินโดรม 3 (Palindrome Partitioning III) ใน C++

ภาพรวมปัญหา

สมมติว่าเรามีสตริง s ที่ประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็ก และจำนวนเต็ม k เราต้องทำตามเงื่อนไขดังนี้:

เปลี่ยนตัวอักษรบางส่วนของ s (ถ้าจำเป็น) ให้เป็นตัวอักษรภาษาอังกฤษพิมพ์เล็กอื่นๆ
แบ่งสตริง s เป็น k ส่วนย่อย (substring) โดยที่แต่ละส่วนย่อยต้องเป็นพาลินโดรม (อ่านจากหน้าหลังได้เหมือนกัน)

เราต้องหาจำนวนตัวอักษรที่ต้องเปลี่ยนน้อยที่สุดเพื่อแบ่งสตริงได้ตามเงื่อนไข

ตัวอย่าง

ถ้า s = "ababbc" และ k = 2 คำตอบคือ 1 เพราะเราต้องเปลี่ยน 1 ตัวอักษร เพื่อแบ่งเป็น 2 พาลินโดรม เช่น เปลี่ยน c เป็น b ได้ "ababbb" แล้วแบ่งเป็น "aba" และ "bbb" หรือเปลี่ยน b ตัวที่ 4 เป็น c ได้ "ababcc" แบ่งเป็น "aba" และ "bcc" (ไม่ใช่พาลินโดรม) - ตัวอย่างที่ถูกต้องคือเปลี่ยน c เป็น b ได้ "ababbb" แบ่ง "aba" และ "bbb"

แนวทางแก้ปัญหา (Dynamic Programming)

สร้างอาร์เรย์ memo ขนาด 105 x 105 สำหรับเก็บผลลัพธ์ย่อย
สร้างฟังก์ชัน solve(s, idx, k, dp) ที่คืนค่าจำนวนการเปลี่ยนขั้นต่ำจากตำแหน่ง idx ด้วย k ส่วนย่อยที่เหลือ
สร้างตาราง dp[n][n] ที่เก็บจำนวนตัวอักษรที่ต้องเปลี่ยนเพื่อให้ substring s[i..j] เป็นพาลินโดรม
ใช้ recursion + memoization เพื่อหาคำตอบที่เหมาะสมที่สุด

ตัวอย่างโปรแกรม

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int memo[105][105];
    
    lli solve(string s, int idx, int k, vector<vector<int>> &dp) {
        if(idx == s.size()) {
            return k == 0 ? 0 : 1000;
        }
        if(memo[idx][k] != -1) return memo[idx][k];
        if(k <= 0) return INT_MAX;
        
        lli ans = INT_MAX;
        for(int i = idx; i < s.size(); i++) {
            ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
        }
        return memo[idx][k] = ans;
    }
    
    int palindromePartition(string s, int k) {
        int n = s.size();
        memset(memo, -1, sizeof(memo));
        vector<vector<int>> dp(n, vector<int>(n));
        
        for(int l = 2; l <= n; l++) {
            for(int i = 0, j = l - 1; j < n; j++, i++) {
                if(l == 2) {
                    dp[i][j] = !(s[i] == s[j]);
                } else {
                    dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
                }
            }
        }
        return solve(s, 0, k, dp);
    }
};

int main() {
    Solution ob;
    cout << (ob.palindromePartition("ababbc", 2));
}

Input