回文串dp|预处理cost

回文串枚举模板

for (int len = 2; len <= n; ++len)
for (int left = 0; left + len <= n; ++left)
int right = left + len - 1;

二维填表min cost时我们会发现需要cost i j，然后就会想到提前预处理计算

(解耦拆分为预处理一次

dp[i][j] = min(dp[i][j], dp[m][j - 1] + cost[m][i - 1]);

lc1278

预处理出任意子串改为回文的最少修改成本

二维dp计算前 i 个字符分割为 j 段回文的最小总成本

最终返回前 n 个字符分割为 k 段的结果

class Solution {
public:
int palindromePartition(string s, int k) {
int n = s.length();
// 替换：计算[left,right]子串改为回文的最少修改数（替代原isPalindrome）
vector<vector<int>> cost(n, vector<int>(n, 0));
for (int len = 2; len <= n; ++len)
for (int left = 0; left + len <= n; ++left) {
int right = left + len - 1;
if (s[left] == s[right]) cost[left][right] = cost[left + 1][right - 1];
elsecost[left][right] = cost[left + 1][right - 1] + 1;
}

// 二维dp[i][j]表示前i个字符分割为j段的最少修改数
vector<vector<int>> dp(n + 1, vector<int>(k + 1, n));
dp[0][0] = 0; // init：前0个字符分割为0段，修改数为0

for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(i, k); ++j) {
if (j == 1) dp[i][1] = cost[0][i - 1];

// 分割为1段的情况
else {
for (int m = j - 1; m < i; ++m) {

// 枚举前m个字符分割为j-1段
dp[i][j] = min(dp[i][j], dp[m][j - 1] + cost[m][i - 1]);
}
}
}
}
return dp[n][k];
}
};

1. 回文判断为成本计算：二维数组 cost ，存储 [left,right] 子串改为回文的最少修改字符数。
​
2. DP二维： dp[i][j] （前 i 个字符分割为 j 段的最少修改数），适配 k 段分割要求
​
3. 重构DP转移逻辑：按 j 段数遍历，枚举分割点计算 j-1 段加当前段的总成本，取最小值

lcr94

1.二维回文表 预处理填写

for (int len = 2; len <= n; ++len)
for (int left = 0; left + len <= n; ++left)

2.典 转移设计

// dp[i] 代表[0, i] 这段最少分隔回文次数

// 求最小，初始化最大为字符串长度，一一切割
vector<int> dp(n, n);
for (int i = 0; i < n; ++i) {
if(isPalindrome[0][i]) dp[i] = 0;
else {
for (int j = 0; j < i; ++j) { // i转移为了j
if (isPalindrome[j + 1][i])
dp[i] = min(dp[i],dp[j] + 1);
}

class Solution {
public:
int minCut(string s)

{
int n = s.length();
vector<vector<bool>> isPalindrome(n, vector<bool>(n));
for (int i = 0; i < n; ++i)

isPalindrome[i][i] = true;

for (int len = 2; len <= n; ++len)
for (int left = 0; left + len <= n; ++left) {
int right = left + len - 1;
if (len == 2)

isPalindrome[left][right] = s[left] == s[right];
if (len > 2) isPalindrome[left][right] = s[left] == s[right] &&isPalindrome[left + 1][right - 1]; //转移
}

// dp[i] 代表[0, i] 这段最少分隔回文次数
// 求最小，初始化最大为字符串长度，一一切割
vector<int> dp(n, n);
for (int i = 0; i < n; ++i) {
if(isPalindrome[0][i]) dp[i] = 0;
else {
for (int j = 0; j < i; ++j) { // i转移为了j
if (isPalindrome[j + 1][i])
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
};

lc1328

class Solution {
public:
string breakPalindrome(string palindrome)
{
int n=palindrome.size();
if(n==1) return "";
int f=n%2;
for(int i=0;i<n;i++)
{
if(f && i==n/2)
continue;
if(palindrome[i]!='a')
{
palindrome[i]='a';
return palindrome;
}
}
palindrome[n-1]='b';
return palindrome;
}
};