Phân hoạch palindrome III trong C++

Cho chuỗi s (chữ thường) và số nguyên k. Cho phép thay đổi ký tự rồi chia chuỗi thành k chuỗi con palindrome. Tìm số ký tự thay đổi tối thiểu.

Ví dụ

s = "ababbc", k = 2 → kết quả 1. Thay 'c' thành 'b' được "aba" và "bbb".

Thuật toán (Dynamic Programming)

1. Tiền xử lý mảng dp[i][j] = số ký tự cần đổi để s[i..j] thành palindrome.
2. DP đệ quy có nhớ solve(idx, k): số thay đổi tối thiểu từ vị trí idx với k đoạn còn lại.
3. Cơ sở: nếu idx == n trả về 0 nếu k==0 else INF.
4. Chuyển trạng thái: thử mọi điểm cắt i, cập nhật ans = min(ans, dp[idx][i] + solve(i+1, k-1)).

Chương trình C++

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

class Solution {
    int memo[105][105];
    long long 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;
        long long ans = INT_MAX;
        for(int i = idx; i < s.size(); i++)
            ans = min(ans, (long long)dp[idx][i] + solve(s, i+1, k-1, dp));
        return memo[idx][k] = ans;
    }
public:
    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 len = 2; len <= n; len++) {
            for(int i = 0, j = len-1; j < n; i++, j++) {
                if(len == 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);
    return 0;
}

Kết quả

1