最长公共子序列的变种：带字符权重的最长公共子序列

题目描述：
给定两个字符串s1和s2，以及一个字符权重映射表，其中每个字符都有一个对应的权重值。要求找到s1和s2的一个公共子序列，使得该子序列中所有字符的权重之和最大。返回这个最大的权重和。

示例：
s1 = "abc", s2 = "acb"
权重映射：a: 5, b: 3, c: 2
最大权重公共子序列可以是"ab"(权重8)或"ac"(权重7)，最大权重和为8。

解题思路：
这个问题是最长公共子序列(LCS)的一个变种，区别在于我们不是简单地计算子序列长度，而是要考虑每个字符的权重值。

步骤分析：

1. 状态定义：
   定义dp[i][j]表示s1的前i个字符和s2的前j个字符的最大权重公共子序列的权重和。

2. 状态转移方程：
   我们需要考虑三种情况：

• 不包含s1的第i个字符：dp[i-1][j]
• 不包含s2的第j个字符：dp[i][j-1]
• 如果s1[i-1] == s2[j-1]，还可以考虑同时包含这两个字符的情况

具体来说：
if s1[i-1] == s2[j-1]:
dp[i][j] = max(dp[i-1][j-1] + weight[s1[i-1]], dp[i-1][j], dp[i][j-1])
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 边界条件：

• dp[0][j] = 0 (s1为空字符串)
• dp[i][0] = 0 (s2为空字符串)

4. 计算顺序：
   从小到大遍历i和j，确保计算dp[i][j]时，dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]都已经计算过。

详细推导过程：

以示例s1="abc", s2="acb"为例：

初始化dp表格：

    "" a c b
""  0  0 0 0
a   0
b   0
c   0

第一步：i=1, j=1 (比较"a"和"a")
字符相同，dp[1][1] = max(0+5, 0, 0) = 5

第二步：i=1, j=2 (比较"a"和"ac")
字符不同，dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 5) = 5

第三步：i=1, j=3 (比较"a"和"acb")
字符不同，dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 5) = 5

继续计算完整表格：

    "" a c b
""  0  0 0 0
a   0  5 5 5
b   0  5 5 8
c   0  5 7 8

最终结果：dp[3][3] = 8

算法复杂度：

• 时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度
• 空间复杂度：O(m×n)，可以使用滚动数组优化到O(min(m,n))

这个算法在标准LCS的基础上，将长度计数改为权重累加，核心思想仍然是动态规划的状态转移和最优子结构性质。