1278. Palindrome Partitioning III

You are given a string s containing lowercase letters and an integer k. You need to :

• First, change some characters of s to other lowercase English letters.
• Then divide s into k non-empty disjoint substrings such that each substring is a palindrome.

Return the minimal number of characters that you need to change to divide the string.

class Solution {
    
    int dp[101][101], cost[101][101];
    int getCost(string& s, int l, int r) {
        if(l >= r) return 0;
        if(cost[l][r] != -1) return cost[l][r];
        return cost[l][r] = (s[l] != s[r]) + getCost(s,l+1,r-1);
    }
    int dfs(string& s, int k, int l) {
        if(dp[k][l] != -1) return dp[k][l];
        if(!k) return dp[k][l] = getCost(s,l,s.length()-1);
        int& res = dp[k][l] = 999999;
        for(int i = l; i < s.length() - k; i++) {
            res = min(res, getCost(s,l,i) + dfs(s,k-1,i+1));
        }
        return res;
    }
public:
    int palindromePartition(string s, int k) {
        memset(dp,-1,sizeof(dp));
        memset(cost,-1,sizeof(cost));
        return dfs(s,k-1,0);
    }
};