回文分割的最小切割次数问题（进阶版：带权值） 题目描述： 给定一个字符串s，以及每个字符的权值数组w（w[ i]表示字符s[ i ]的权值）。我们需要将字符串分割成若干个子串，使得每个子串都是回文串。每次切割的代价等于被切割位置左侧所有字符的权值之和乘以右侧所有字符的权值之和。要求找到一种分割方式，使得所有切割代价的总和最小。 例如：s = "abc", w = [ 1,2,3 ] 可能的切割方式： 不切割："abc"不是回文，无效 切为"a","b","c"：需要2次切割 第一次在a后切：代价 = 1 × (2+3) = 5 第二次在b后切：代价 = (1+2) × 3 = 9 总代价 = 5 + 9 = 14 切为"a","bc"："bc"不是回文，无效 切为"ab","c"："ab"不是回文，无效 解题过程： 问题分析： 我们需要将字符串分割成多个回文子串 每次切割都有代价，代价计算与权值相关 目标是找到使总切割代价最小的分割方案 状态定义： 定义dp[ i][ j]表示子串s[ i..j ]被分割成回文子串的最小总切割代价。 状态转移： 如果s[ i..j]本身是回文，那么dp[ i][ j ] = 0（不需要切割） 否则，我们需要在i和j之间的某个位置k进行切割： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + cost(i,k))，其中i ≤ k < j 其中cost(i,k)表示在位置k后切割的代价： cost(i,k) = (w[ i] + w[ i+1] + ... + w[ k]) × (w[ k+1] + ... + w[ j ]) 预处理： 预处理前缀和数组prefix，prefix[ i ]表示前i个字符的权值和 预处理回文判断数组isPalindrome[ i][ j]，表示s[ i..j ]是否是回文 计算顺序： 按区间长度从小到大计算 示例计算（s = "aba", w = [ 1,2,1 ]）： 区间长度1：所有单字符都是回文，代价为0 区间长度2： "ab"：不是回文，需要在a后切割 代价 = dp[ 0][ 0] + dp[ 1][ 2 ] + cost(0,0) = 0 + ? + (1)×(2+1) = 3 "ba"：类似处理 区间长度3： "aba"：本身是回文，代价为0 通过这种动态规划方法，我们可以高效地找到最小代价的回文分割方案。