回文分割的最小切割次数问题（进阶版：带权值） 题目描述 给定一个字符串 s 和一个权值数组 w ，其中 w[i] 表示以 s[i] 为中心（或左中心）的回文子串的权值。要求将 s 分割成若干回文子串，使得每个回文子串的权值之和最大，并返回最大权值和。注意：每个回文子串必须至少包含一个字符，且权值计算基于子串的中心位置。 解题过程 问题分析 本题是回文分割问题的变种，目标不再是求最小切割次数，而是最大化分割后回文子串的权值和。需要结合区间动态规划判断回文子串，并记录区间内的最大权值和。 定义状态 设 dp[i][j] 表示子串 s[i:j+1] 分割后能获得的最大权值和。 设 is_pal[i][j] 表示子串 s[i:j+1] 是否为回文串（布尔值）。 状态转移 若 s[i:j+1] 是回文串，则 dp[i][j] 可直接取该子串的权值（即 w[(i+j)//2] ）。 否则，枚举分割点 k （ i ≤ k < j ），将子串分割为 s[i:k+1] 和 s[k+1:j] ，则： dp[i][j] = max(dp[i][k] + dp[k+1][j]) 综合两种情况： dp[i][j] = max(is_pal[i][j] ? w[(i+j)//2] : 0, max_{k=i}^{j-1}(dp[i][k] + dp[k+1][j])) 初始化与边界 单字符子串一定是回文串： dp[i][i] = w[i] ， is_pal[i][i] = True 。 空子串权值为0： dp[i][j] = 0 （当 i > j ）。 双字符子串回文判断： is_pal[i][i+1] = (s[i] == s[i+1]) 。 计算顺序 按子串长度 len 从小到大的顺序计算： 先计算所有 is_pal[i][j] （通过中心扩展或动态规划）。 再计算 dp[i][j] ，依赖更短的子串结果。 示例 设 s = "aba" ， w = [1, 2, 3] ： 单字符回文权值： dp[0][0]=1 ， dp[1][1]=2 ， dp[2][2]=3 。 子串 "ab" ：非回文，分割为 "a"+"b" ，权值和=1+2=3。 子串 "ba" ：非回文，权值和=2+3=5。 子串 "aba" ：是回文，权值=中心 w[1]=2 ；分割为 "a"+"ba" （权值和=1+5=6）或 "ab"+"a" （3+1=4），取最大值6。最终 dp[0][2] = max(2, 6) = 6 。 复杂度 时间复杂度 O(n³)（枚举区间和分割点），空间复杂度 O(n²)。可通过预处理回文子串优化至 O(n²)。