区间动态规划例题：最长公共子序列问题（带权重版本） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符权重表 weight （每个字符对应一个整数权重）。要求找到 s1 和 s2 的最长公共子序列（LCS），但 不是 简单地计算长度，而是计算所有公共子序列中 权重和最大 的那个子序列的权重和。 例如： s1 = "abc" , s2 = "ac" , weight = {'a': 1, 'b': 2, 'c': 3} 公共子序列有 "a" （权重1）、 "c" （权重3）、 "ac" （权重1+3=4）。 最大权重和为4（对应子序列 "ac" ）。 解题过程 问题分析 经典LCS问题是求最长公共子序列的长度，本题变体为 带权重的最大权重公共子序列 。 若两个字符匹配，不仅增加长度1，还增加该字符的权重。 目标：在 s1[0..m-1] 和 s2[0..n-1] 上，找到权重和最大的公共子序列。 状态定义 定义 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0:i] ）与 s2 的前 j 个字符（即 s2[0:j] ）的 最大权重公共子序列的权重和 。 注意： i 和 j 分别表示前缀长度（从0开始），当 i=0 或 j=0 时，表示空子序列，权重和为0。 状态转移方程 Case 1: s1[i-1] == s2[j-1] （当前字符匹配） 匹配的字符 c = s1[i-1] 权重为 w = weight[c] 。 我们可以选择将 c 纳入公共子序列，则权重增加 w ，并加上前驱状态 dp[i-1][j-1] ： dp[i][j] = dp[i-1][j-1] + w Case 2: s1[i-1] != s2[j-1] （当前字符不匹配） 最大权重公共子序列不可能同时包含 s1[i-1] 和 s2[j-1] ，但可能： 排除 s1[i-1] ，考虑 s1[0:i-1] 和 s2[0:j] ： dp[i-1][j] 排除 s2[j-1] ，考虑 s1[0:i] 和 s2[0:j-1] ： dp[i][j-1] 取最大值： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 初始化 dp[0][j] = 0 （对任意 j ，空字符串与 s2 前缀的公共子序列权重和为0） dp[i][0] = 0 （对任意 i ， s1 前缀与空字符串的公共子序列权重和为0） 计算顺序 按 i 从 0 到 m ， j 从 0 到 n 的顺序填表（ m = len(s1) , n = len(s2) ）。 最终答案在 dp[m][n] 。 示例演算 s1 = "abc" , s2 = "ac" , weight = {'a':1, 'b':2, 'c':3} 建表 dp[4][3] （因 m=3 , n=2 ，但维度为 (m+1) x (n+1) ） | i\j | 0 | 1 (a) | 2 (c) | |-----|----|-------|-------| | 0 | 0 | 0 | 0 | | 1 (a) | 0 | 1 | 1 | | 2 (b) | 0 | 1 | 1 | | 3 (c) | 0 | 1 | 4 | 计算过程： i=1, j=1 : s1[0]='a' 匹配 s2[0]='a' → dp[1][1] = dp[0][0] + 1 = 1 i=1, j=2 : 'a' != 'c' → max(dp[0][2]=0, dp[1][1]=1) = 1 i=2, j=1 : 'b' != 'a' → max(dp[1][1]=1, dp[2][0]=0) = 1 i=2, j=2 : 'b' != 'c' → max(dp[1][2]=1, dp[2][1]=1) = 1 i=3, j=1 : 'c' != 'a' → max(dp[2][1]=1, dp[3][0]=0) = 1 i=3, j=2 : 'c' == 'c' → dp[3][2] = dp[2][1] + 3 = 1 + 3 = 4 结果： dp[3][2] = 4 ，符合预期。 复杂度分析 时间复杂度：O(mn)，需要填充 m×n 的DP表。 空间复杂度：O(mn)，可优化至 O(min(m,n))（只保留当前行和上一行）。 关键点 本题在经典LCS的“长度”基础上，将“+1”改为“+weight[ c ]”，其余逻辑一致。 若权重全为1，则退化为经典LCS长度问题。