最小成本回文串分割问题（带权值版本）
字数 1342 2025-12-01 23:22:06
最小成本回文串分割问题（带权值版本）
题目描述：
给定一个字符串s和一个权值数组cost，其中cost[i]表示将字符s[i]单独作为一个回文子串的代价。我们需要将字符串s分割成若干回文子串，使得所有回文子串的代价之和最小。其中每个回文子串的代价等于该子串中所有字符的cost值之和。
解题过程：
- 问题分析：
- 输入：字符串s（长度为n），权值数组cost（长度为n）
- 输出：最小总代价
- 目标：将s分割成若干个回文子串，使得所有子串的代价和最小
- 每个回文子串的代价是该子串中所有字符的cost值之和
-
状态定义：
定义dp[i]表示将前i个字符（s[0...i-1]）分割成回文子串的最小总代价。 -
状态转移方程：
对于每个位置i（1 ≤ i ≤ n），我们需要考虑所有可能的回文子串s[j...i-1]（0 ≤ j ≤ i-1）：
- 如果s[j...i-1]是回文串，那么dp[i] = min(dp[i], dp[j] + sum(cost[j...i-1]))
- 其中sum(cost[j...i-1])表示从位置j到i-1的所有cost值之和
- 初始化：
- dp[0] = 0（空字符串的代价为0）
- 对于i > 0，初始时设dp[i]为一个很大的数（如无穷大）
- 回文判断预处理：
为了高效判断子串是否为回文串，我们可以预先计算一个二维数组isPalindrome：
- isPalindrome[i][j]表示子串s[i...j]是否为回文串
- 计算方法：对于长度为1的子串，都是回文串；对于长度为2的子串，判断两个字符是否相等；对于更长的子串，isPalindrome[i][j] = (s[i] == s[j]) && isPalindrome[i+1][j-1]
- 前缀和预处理：
为了快速计算子串的代价和，我们可以预先计算前缀和数组prefixSum：
- prefixSum[i] = cost[0] + cost[1] + ... + cost[i-1]
- 子串s[j...i-1]的代价和 = prefixSum[i] - prefixSum[j]
-
算法步骤：
(1) 预处理isPalindrome数组
(2) 计算前缀和数组prefixSum
(3) 初始化dp数组
(4) 遍历i从1到n：- 遍历j从0到i-1：
- 如果isPalindrome[j][i-1]为真：
- 当前代价 = dp[j] + (prefixSum[i] - prefixSum[j])
- dp[i] = min(dp[i], 当前代价)
(5) 返回dp[n]作为结果
- 如果isPalindrome[j][i-1]为真：
- 遍历j从0到i-1：
-
时间复杂度：O(n²)，空间复杂度：O(n²)
-
示例验证：
假设s = "aab", cost = [1, 2, 3]
- 可能的分割方式：
- ["a","a","b"]：代价 = (1) + (2) + (3) = 6
- ["aa","b"]：代价 = (1+2) + (3) = 6
- ["a","ab"]：但"ab"不是回文串，无效
- 最小代价为6
这个算法通过动态规划有效地解决了带权值的最小回文分割问题，确保了最优解的正确性。