得到 K 个半回文串的最少修改次数-JZTXT

给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个子字符串，使得每个子字符串变成半回文串需要修改的字符数目最少。
请你返回一个整数，表示需要修改的最少字符数目。

1. 动态规划

class Solution {
public:
    int minimumChanges(string s, int k) {
        int n = s.size();
        //计算字符串转化为半回文串最小修改次数
        function<int(string)> get = [&](string str){
            int n = str.size();
            int res = INT_MAX;
            for(int d=1;d<=n/2;d++){
                if(n%d!=0) continue;
                int cnt = 0;
                for(int i=0;i<d;i++){//不同的起始位置
                    string cur = "";
                    for(int j=i;j<n;j=j+d)
                        cur.push_back(str[j]);
                    for(int j=0;j<cur.size()/2;j++)
                        cnt += (cur[j]!=cur[cur.size()-j-1]);
                }
                res = min(res,cnt);
            }
            return res;
        };
        //预先计算任意子串最小修改次数
        int modify[n][n];
        memset(modify,INT_MAX,sizeof(modify));//计算任意子串最小修改次数
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                modify[i][j] = get(s.substr(i,j-i+1));
                
        //动态规划，dp[i][j]表示以i位置作为第j段结尾的最小修改次数
        int dp[n+1][k+1];
        memset(dp,100,sizeof(dp));
        dp[0][0] = 0;
 
        for(int i=1;i<=n;i++){//遍历每一个位置
            for(int j=1;j<=k;j++){//遍历每一个段
                for(int l=1;l<i;l++){//l-i作为当前段
                    if(modify[l-1][i-1]==INT_MAX) continue;
                    dp[i][j] = min(dp[i][j],dp[l-1][j-1]+modify[l-1][i-1]);
                }
            }
        }
        return dp[n][k];
    }
};

回文