c1 = word1[i-1], c2 = word2[j-1]
w = charWeight[c1 - 'a'] // 注意，仅在c1==c2时w有意义
if c1 == c2:
    dp[i][j] = max(dp[i-1][j-1] + w, dp[i-1][j], dp[i][j-1])
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

好的，我将为你讲解一个线性动态规划领域内，且不在你已记录列表中的经典问题。 题目：最少操作使字符串相同（Delete Operation for Two Strings）的变种——带字符权重的最少删除操作 题目描述 给你两个字符串 word1 和 word2 ，以及一个长度为26的整数数组 charWeight ，其中 charWeight[i] 表示字母 'a' + i 的“删除代价”。 你可以对两个字符串进行任意次删除操作。每次操作可以删除任意一个字符串中的一个字符，并需要支付该字符对应的删除代价。 请你计算并返回使 word1 和 word2 相同所需的 最小总删除代价 。 两个字符串「相同」 是指：在删除某些字符（代价可能不同）后，两个字符串剩余的字符序列完全相同。 示例1： 输入： word1 = "sea" word2 = "eat" charWeight = [ 1,1,1,... ] // 默认所有字符代价为1 输出：2 解释：将"sea"中的's'（代价1）删除，将"eat"中的't'（代价1）删除，剩下"ea"，总代价为2。 示例2（引入权重）： 输入： word1 = "delete" word2 = "leet" charWeight = [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26 ] // a=1, b=2,... z=26 输出：30 解释： 一种方案： 从"delete"中删除字符：'d'(代价4), 'e'(删除第一个e，代价5)，剩下"let"。 从"leet"中删除字符：'l'(代价12), 'e'(代价5)，剩下"et"。 此时两个字符串不相等。显然这不是最优的。 让我们思考最优方案。 解题思路 这个题目是经典“两个字符串的最小删除和”（LeetCode 583）的加权版本。其核心思想是： 问题转化 ：使两个字符串相同的最小删除代价， 等价于 找到两个字符串的一个 公共子序列 ，使得删除掉 不是 这个公共子序列的所有字符的 总代价最小 。 等价目标 ：换句话说，如果我们能找到这样一个公共子序列，使得构成它所需删除的字符（即不在该子序列中的字符）代价之和最小，那么剩下的两个字符串就完全相同了。 进一步转化 ：设字符串所有字符的总权重为 totalWeight ，公共子序列的字符权重和为 lcsWeight 。那么删除的代价 = totalWeight(word1) + totalWeight(word2) - 2 * lcsWeight 。 为什么乘以2？因为要删除两个字符串中所有不属于这个公共子序列的字符。这个公式是解题的关键。 新目标 ：因此，原问题转化为：寻找两个字符串的 一个公共子序列 ，使得该子序列的 字符权重和最大 。这是一个 带权重的 最长公共子序列（Weighted LCS）问题。 解题步骤（动态规划） 我们定义动态规划状态 dp[i][j] 。 第1步：状态定义 dp[i][j] 表示：考虑 word1 的前 i 个字符（下标 1 到 i）和 word2 的前 j 个字符（下标 1 到 j），它们所能形成的 权重和最大的公共子序列 的权重值。 这里我们使用 1-indexed 的思考方式，方便处理空字符串情况。 第2步：状态初始化 考虑边界情况： 当 i = 0 时， word1 的前缀是空字符串。空字符串和任何字符串的公共子序列只能是空字符串，其权重和为 0。所以 dp[0][j] = 0 (0 ≤ j ≤ n)。 同理，当 j = 0 时， word2 的前缀是空字符串， dp[i][0] = 0 (0 ≤ i ≤ m)。 其中 m = word1.length() , n = word2.length() 。 第3步：状态转移方程 对于当前位置 (i, j) ，对应字符 c1 = word1[i-1] , c2 = word2[j-1] （因为我们的状态是1-indexed，而字符串是0-indexed）。 我们考虑如何从之前的状态推导出 dp[i][j] ： 情况一：字符相等（ c1 == c2 ） 最优的公共子序列 可以 包含这个字符。 如果包含它，那么它的权重 w = charWeight[c1 - 'a'] 会加入到子序列中。在包含它之前，我们需要看 word1 前 i-1 个字符和 word2 前 j-1 个字符的最大权重公共子序列，即 dp[i-1][j-1] 。 所以，包含这个字符的候选值为 dp[i-1][j-1] + w 。 当然，我们也可以选择不包含这个字符，那么状态就从 dp[i-1][j] 或 dp[i][j-1] 转移而来。但我们要求最大值，所以会取所有可能的最大值。 转移方程为： dp[i][j] = max(dp[i-1][j-1] + w, dp[i-1][j], dp[i][j-1]) 情况二：字符不相等（ c1 != c2 ） 当前两个字符不可能同时被包含在公共子序列中。 那么，最大权重公共子序列要么来自 word1 的前 i-1 个和 word2 的前 j 个（即舍弃 c1 ），要么来自 word1 的前 i 个和 word2 的前 j-1 个（即舍弃 c2 ）。 转移方程为： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 综合起来，状态转移方程可以统一为： 第4步：计算顺序与最终答案 计算顺序 ：由于 dp[i][j] 依赖于 dp[i-1][j-1] , dp[i-1][j] , dp[i][j-1] ，我们可以按 i 从 1 到 m， j 从 1 到 n 的双重循环顺序来计算。 计算最大权重公共子序列和 ：最终， dp[m][n] 就是我们要求的 最大权重公共子序列的权重和 ，记为 maxLCSWeight 。 计算总删除代价 ： 计算 word1 的总权重 sum1 。 计算 word2 的总权重 sum2 。 最小总删除代价 = sum1 + sum2 - 2 * maxLCSWeight 。 第5步：示例演算（示例2） word1 = "delete" (d,e,l,e,t,e) word2 = "leet" (l,e,e,t) 权重：a=1, b=2, ..., d=4, e=5, l=12, t=20. 初始化 dp[0][j]=0 , dp[i][0]=0 。 计算 dp 表 (过程简略，展示关键点)： dp[1][1] : 'd' vs 'l'，不等， max(dp[0][1]=0, dp[1][0]=0)=0 。 dp[2][2] : word1的'e'(5) vs word2的'e'(5)，相等。 max(dp[1][1]+5=5, dp[1][2]=0, dp[2][1]=0) = 5 。 dp[3][1] : 'l'(12) vs 'l'(12)，相等。 max(dp[2][0]+12=12, dp[2][1]=0, dp[3][0]=0) = 12 。 ... 最终计算得到 dp[6][4] (即考虑整个字符串)。 尝试寻找最优公共子序列 ：观察字符串，一个可能的权重很大的公共子序列是 "let" (l=12, e=5, t=20)，其权重和为 37。另一个可能是 "leet" 但 word1 中没有连续的两个 'e' 和 't' 跟在 'l' 和第一个 'e' 后面，构不成 "leet" 。 "lee" 的权重是 12+5+5=22。 "let" 的 37 看起来很有竞争力。 最终 dp[6][4] 计算结果应为 37 （对应公共子序列 "let" ，在word1中是第3、4、5个字符? 验证：word1: d(4), e(5), l(12), e(5), t(20), e(5). 取 l(12), e(5), t(20) 权重和37。word2: l(12), e(5), e(5), t(20). 取 l(12), e(第二个e，5), t(20) 权重和37。匹配成功。）。 计算总权重 ： sum1 = 4+5+12+5+20+5 = 51 sum2 = 12+5+5+20 = 42 计算答案 ： 最小总删除代价 = 51 + 42 - 2 * 37 = 93 - 74 = 19 。 让我们验证一下这个19的代价方案： 从 "delete" 中删除：'d'(4), 第一个'e'(5), 最后一个'e'(5)。剩下 "let" 。删除代价 4+5+5=14。 从 "leet" 中删除：第二个'e'(5)。剩下 "let" 。删除代价5。 总代价 14+5=19。并且两个字符串都变成了 "let" 。这是正确的。 注意 ：示例2最初给出的输出30是基于一个错误的手算假设。通过动态规划，我们得到了更优解19。 总结 这个问题的核心在于 两次转化 ： 将 最小删除代价 问题转化为 最大权重公共子序列 问题。 使用动态规划解决带权重的LCS。 状态 dp[i][j] 设计巧妙，转移方程清晰地刻画了“当前字符是否被选入最优公共子序列”的决策过程。最后通过总权重减去两倍的公共子序列权重和得到最终答案，思维过程非常连贯，是线性动态规划中一个经典的变种问题。