带权值的最长回文子序列（最大化回文子序列权重）

题目描述
给定一个字符串 s，长度为 n，每个位置 i 的字符 s[i] 对应一个正权重 w[i]。
需要找出一个回文子序列（不一定连续，但相对顺序必须与原字符串一致），使得这个回文子序列中所有字符的权重之和最大，并返回这个最大权重和。
注意：空序列视为回文，但权重和为 0。
如果回文子序列长度为 1，其权重就是该字符的权重。

示例

s = "abac"
w = [3, 2, 5, 1]

可能的回文子序列：

• "a"（第一个 'a'），权重 3
• "aba"（字符索引 0,1,2），权重 3+2+5=10
• "aca"（索引 0,2,3），权重 3+5+1=9
• "b" 权重 2
• "c" 权重 1
  等等。
  最大权重和为 10（对应 "aba"）。

解题思路
这是一个区间动态规划的变体。
定义 dp[i][j] 表示在子串 s[i..j]（闭区间）中，能得到的最大权重的回文子序列的权重和。
最终答案是 dp[0][n-1]。

状态转移
考虑区间 [i, j]：

1. 如果 i == j，只有一个字符，回文子序列就是它自己，dp[i][j] = w[i]。

2. 如果 i > j，空区间，dp[i][j] = 0（但我们的循环通常 i <= j，所以可以不显式定义，只在 i > j 时默认为 0）。

3. 一般情况（i < j）：

   • 如果 s[i] == s[j]，那么这两个字符可以同时作为回文子序列的首尾，内部区间 [i+1, j-1] 取最优解，再加上这两个字符的权重：
     dp[i][j] = dp[i+1][j-1] + w[i] + w[j]。
   • 如果 s[i] != s[j]，那么它们不能同时作为首尾，有两种选择：
     • 不取 s[i]，只考虑区间 [i+1, j] 的最优解。
     • 不取 s[j]，只考虑区间 [i, j-1] 的最优解。
     • 注意：还可以两个都不取，只取内部区间 [i+1, j-1] 的解，但这种情况已经被上述两种情况覆盖（因为 dp[i+1][j] 和 dp[i][j-1] 都可能不取端点，包括只取内部的情况）。
       因此：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

   但这里有一个关键点：即使 s[i] == s[j]，我们也可以选择不取它们同时作为首尾，而只取其中一个或都不取。所以更严谨的状态转移是：

   dp[i][j] = max(dp[i+1][j], dp[i][j-1])  // 不取 i 或不取 j
   如果 s[i] == s[j]:
       dp[i][j] = max(dp[i][j], dp[i+1][j-1] + w[i] + w[j])
   

   另外，当区间长度=2时，i+1 可能大于 j-1，此时 dp[i+1][j-1] 应视为 0。

初始化
单个字符区间：dp[i][i] = w[i]。
其余为 0（后续计算会覆盖）。

计算顺序
因为 dp[i][j] 依赖 dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1]，即依赖更短的区间（长度更小），所以按区间长度从小到大计算。

逐步推导
以 s = "abac", w = [3,2,5,1] 为例：

n=4，dp 表大小 4×4。

1. 初始化单个字符：

   • dp[0][0] = 3
   • dp[1][1] = 2
   • dp[2][2] = 5
   • dp[3][3] = 1

2. 长度=2：

   • [0,1]: s[0]='a', s[1]='b'，不相等
     dp[0][1] = max(dp[1][1], dp[0][0]) = max(2,3)=3
   • [1,2]: 'b' 和 'a' 不等
     dp[1][2] = max(dp[2][2], dp[1][1]) = max(5,2)=5
   • [2,3]: 'a' 和 'c' 不等
     dp[2][3] = max(dp[3][3], dp[2][2]) = max(1,5)=5

3. 长度=3：

   • [0,2]: s[0]='a', s[2]='a' 相等
     先算：dp[0][2] = max(dp[1][2], dp[0][1]) = max(5,3)=5
     再考虑相等：dp[1][1]=2，所以 dp[0][2] = max(5, 2+3+5=10) = 10
   • [1,3]: s[1]='b', s[3]='c' 不等
     dp[1][3] = max(dp[2][3], dp[1][2]) = max(5,5)=5

4. 长度=4：

   • [0,3]: s[0]='a', s[3]='c' 不等
     dp[0][3] = max(dp[1][3], dp[0][2]) = max(5,10)=10

结果：dp[0][3] = 10，与示例一致。

状态转移公式总结

dp[i][i] = w[i]
对于长度 len 从 2 到 n：
  对于 i 从 0 到 n-len：
      j = i+len-1
      dp[i][j] = max(dp[i+1][j], dp[i][j-1])
      如果 s[i] == s[j]：
          内部 = 0 如果 i+1 > j-1 否则 dp[i+1][j-1]
          dp[i][j] = max(dp[i][j], 内部 + w[i] + w[j])

最终答案：dp[0][n-1]

复杂度
时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n)，但这里不展开）。

关键点

• 本质是带权值的最长回文子序列，与经典最长回文子序列的区别是每个字符有权重，目标是最大化权重和而非长度。
• 当首尾字符相等时，可以同时选取它们，并加上内部区间的最优解。
• 即使首尾相等，也可以不选它们（通过 max(dp[i+1][j], dp[i][j-1]) 覆盖这种情况）。