区间动态规划例题：最长公共子序列问题（带权重版本） 题目描述 给定两个字符串 text1 和 text2 ，以及一个权重函数 w(c1, c2) ，表示当字符 c1 （来自 text1 ）与字符 c2 （来自 text2 ）匹配时的权重值。求两个字符串的公共子序列中，所有匹配字符的权重之和的最大值。公共子序列的定义是：原字符串中删除某些字符（也可以不删除）后，剩余字符的相对位置保持不变。 示例 输入： text1 = "abcde" text2 = "ace" 权重函数： w(c1, c2) = 1 （如果 c1 == c2 ），否则 w(c1, c2) = 0 输出： 3 （公共子序列为 "ace" ，权重和为 1+1+1=3 ） 解题过程 定义状态 设 dp[i][j] 表示 text1 的前 i 个字符（即 text1[0:i-1] ）与 text2 的前 j 个字符（即 text2[0:j-1] ）的公共子序列的最大权重和。注意： i 和 j 可以为 0，表示空子串。 状态转移方程 考虑如何从已知状态推导 dp[i][j] ： 如果 text1[i-1] == text2[j-1] ： 当前字符匹配，可以选择匹配它们，权重增加 w(text1[i-1], text2[j-1]) ，然后加上 dp[i-1][j-1] 的最大权重和。 也可以选择不匹配它们（跳过其中一个或两个），此时权重不变，取其他情况的最大值。 因此： dp[i][j] = max(dp[i-1][j-1] + w(text1[i-1], text2[j-1]), dp[i-1][j], dp[i][j-1]) 如果 text1[i-1] != text2[j-1] ： 当前字符不匹配，只能跳过其中一个字符，取 dp[i-1][j] 或 dp[i][j-1] 的最大值： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 初始化 当 i=0 或 j=0 时，表示一个字符串为空，公共子序列的最大权重和为 0： dp[0][j] = 0 （对任意 j ） dp[i][0] = 0 （对任意 i ） 计算顺序 由于 dp[i][j] 依赖于 dp[i-1][j-1] 、 dp[i-1][j] 、 dp[i][j-1] ，需要按 i 从 1 到 len(text1) ， j 从 1 到 len(text2) 的顺序计算。 最终结果 结果存储在 dp[len(text1)][len(text2)] 中，表示整个字符串的最大权重和。 示例推导 以 text1 = "abcde" 、 text2 = "ace" 、 w(c1, c2) = 1 if c1==c2 else 0 为例： 初始化： dp[0][j] = 0 ， dp[i][0] = 0 。 计算 dp[1][1] （ text1[0]='a' ， text2[0]='a' ）： 匹配： dp[0][0] + 1 = 1 ；不匹配： max(dp[0][1]=0, dp[1][0]=0)=0 → dp[1][1]=1 。 类似地，逐步填充表格，最终 dp[5][3] = 3 。 总结 本题通过动态规划将问题分解为子问题，利用匹配与否的决策，逐步构建最优解。权重函数的引入使得问题更通用，适用于实际场景中的加权匹配需求。