区间动态规划例题：最长公共子序列问题（带权重版本）
题目描述：
给定两个字符串s1和s2，以及每个字符的权重值。要求找出这两个字符串的最长公共子序列，但这里不是简单地计算长度，而是计算所有公共子序列中权重和最大的那个子序列的权重值。每个字符的权重用一个映射表给出。
解题过程：
-
问题分析
这是一个带权重的最长公共子序列问题。与标准LCS问题不同，我们不仅要找到公共子序列，还要找到权重和最大的那个。我们需要使用区间动态规划来解决。 -
定义状态
设dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符所形成的带权重最大公共子序列的权重和。 -
状态转移方程
-
如果s1[i-1] == s2[j-1]（字符匹配）：
dp[i][j] = dp[i-1][j-1] + weight[s1[i-1]]
这里我们加上匹配字符的权重 -
如果s1[i-1] != s2[j-1]（字符不匹配）：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
取删除s1当前字符或删除s2当前字符的较大值
- 边界条件
- dp[0][j] = 0（s1为空字符串）
- dp[i][0] = 0（s2为空字符串）
- 具体示例
假设：
s1 = "ABC", s2 = "ACB"
权重：A=1, B=2, C=3
初始化dp表：
0 A C B
0 0 0 0 0
A 0
B 0
C 0
逐步计算：
(1,1): A=A → dp[1][1] = 0 + 1 = 1
(1,2): A≠C → dp[1][2] = max(0, 1) = 1
(1,3): A≠B → dp[1][3] = max(0, 1) = 1
(2,1): B≠A → dp[2][1] = max(1, 0) = 1
(2,2): B≠C → dp[2][2] = max(1, 1) = 1
(2,3): B=B → dp[2][3] = 1 + 2 = 3
(3,1): C≠A → dp[3][1] = max(1, 0) = 1
(3,2): C=C → dp[3][2] = 1 + 3 = 4
(3,3): C≠B → dp[3][3] = max(4, 3) = 4
最终结果为4，对应子序列"AC"（权重1+3=4）或"AB"（权重1+2=3）中的较大值。
- 算法实现要点
- 使用二维数组存储中间结果
- 按行或按列顺序填充dp表
- 时间复杂度O(m×n)，空间复杂度O(m×n)
- 可以通过滚动数组优化空间复杂度到O(min(m,n))
- 结果重构
如果需要找出具体的最大权重公共子序列，可以从dp[m][n]开始反向追踪，根据状态转移的选择路径来重建子序列。