千问 LeetCode 1278.分割回文串 ||| public int palindromePartition(String s, int k)

这道题是 LeetCode 1278属于动态规划Dynamic Programming的经典题目通常被称为“双DP”问题。 核心思路这道题需要我们将字符串 s 分割成 k 个回文子串并求出最少需要修改的字符数。我们可以将问题拆解为两个部分预处理计算代价 计算任意一个子串 s[i…j] 变成回文串需要修改多少次。主动态规划寻找最优解 计算前 i 个字符分割成 k 个回文串的最小代价。 详细步骤第一步预处理子串变成回文的代价我们需要一个二维数组 cost[i][j]表示将子串 s[i…j] 变为回文串所需的最小修改次数。状态转移如果 s[i] s[j]则 cost[i][j] cost[i1][j-1]首尾相同不需要修改看中间。如果 s[i] ! s[j]则 cost[i][j] cost[i1][j-1] 1首尾不同修改其中一个次数1。计算顺序 从短子串到长子串或者从后往前遍历。第二步主动态规划定义 dp[i][j] 表示将字符串的前 i 个字符即 s[0…i-1]分割成 j 个非空回文子串所需的最小修改次数。状态转移方程我们要计算 dp[i][j]可以枚举最后一个回文子串的起始位置 m。假设最后一个子串是 s[m…i-1]那么前面的 s[0…m-1] 就必须被分割成 j-1 个回文子串。dp[i][j] min(dp[m][j-1] cost[m][i-1])其中 m 的取值范围是 j-1 到 i-1保证前面至少能分出 j-1 个字符。初始化dp[i][1]表示前 i 个字符分成 1 个回文串代价就是 cost[0][i-1]。其他位置初始化为一个极大值如 Integer.MAX_VALUE。 Java 代码实现class Solution {public int palindromePartition(String s, int k) {int n s.length();// 1. 预处理计算 cost[i][j]即子串 s[i...j] 变成回文需要的修改次数 int[][] cost new int[n][n]; // 从后往前遍历确保计算 cost[i][j] 时cost[i1][j-1] 已经计算过 for (int i n - 2; i 0; i--) { for (int j i 1; j a (0) bc (1) 1。 * m2: dp[2][1] cost[2][2] - ab (1) c (0) 1。 * 取最小值 1。