最少操作使字符串相同（Delete Operation for Two Strings）的变种——带字符权重的最少删除操作

题目描述
给定两个字符串 word1 和 word2，以及两个整数数组 cost1 和 cost2，其中 cost1[i] 表示删除 word1 中第 i 个字符的代价，cost2[j] 表示删除 word2 中第 j 个字符的代价。你的目标是通过删除两个字符串中的某些字符，使得 word1 和 word2 完全相同。每次删除操作可以删除任意一个字符串中的任意一个字符，删除该字符需要支付对应的代价。请计算使两个字符串相同所需的最小总代价。

注意：删除操作后，剩余字符的相对顺序保持不变，最终两个字符串必须完全相同。

示例
输入：
word1 = "sea"
word2 = "eat"
cost1 = [1, 2, 3]
cost2 = [4, 5, 6]
输出：7
解释：
删除 's' 和 'a' 从 word1（代价 1 + 3 = 4），删除 't' 从 word2（代价 6），总代价 4 + 6 = 10 并不是最小。
实际上，最优方案是：保留 "ea"，删除 word1 的 's'（代价 1），删除 word2 的 't'（代价 6），总代价 7。

解题过程

这个问题是“两个字符串的最小删除距离”问题的加权版本。在标准问题中，每个字符的删除代价是 1，目标是使两个字符串相同所需的最小删除次数。而这里每个字符的删除代价不同，因此我们需要在动态规划中考虑代价权重。

步骤 1：问题分析与思路
要使两个字符串相同，我们实际上需要找到它们的最长公共子序列（LCS），因为公共子序列中的字符不需要删除，而其他字符都需要删除。但这里我们并不是简单计算最长公共子序列的长度，而是要最小化删除的总代价。
等价地，我们可以将问题转化为：保留一个公共子序列，使得保留的字符对应的删除代价总和最大（即尽量保留删除代价大的字符），因为删除的总代价 = 所有字符的总代价 - 保留的字符的总代价。
更直接的方法是定义动态规划状态，表示处理到两个字符串的某个位置时，使它们相同的最小删除代价。

步骤 2：定义状态
设 dp[i][j] 表示将 word1 的前 i 个字符（即 word1[0..i-1]）和 word2 的前 j 个字符（即 word2[0..j-1]）变为相同所需的最小删除代价。
其中 i 和 j 可以为 0，表示空字符串。

步骤 3：状态转移方程
考虑当前处理的字符 word1[i-1] 和 word2[j-1]：

1. 如果 word1[i-1] == word2[j-1]，则这两个字符可以匹配，不需要删除它们。此时最小代价等于将前面部分变为相同的代价，即 dp[i][j] = dp[i-1][j-1]。
2. 如果 word1[i-1] != word2[j-1]，则我们有两种选择：
   • 删除 word1[i-1]，代价为 cost1[i-1]，然后处理 word1 的前 i-1 个字符和 word2 的前 j 个字符，总代价为 dp[i-1][j] + cost1[i-1]。
   • 删除 word2[j-1]，代价为 cost2[j-1]，然后处理 word1 的前 i 个字符和 word2 的前 j-1 个字符，总代价为 dp[i][j-1] + cost2[j-1]。
     我们取这两种选择的最小值：dp[i][j] = min(dp[i-1][j] + cost1[i-1], dp[i][j-1] + cost2[j-1])。

步骤 4：边界条件

• 当 i = 0 且 j = 0 时，两个都是空字符串，已经相同，删除代价为 0：dp[0][0] = 0。
• 当 i = 0 但 j > 0 时，word1 是空字符串，要使它们相同，必须删除 word2 的所有前 j 个字符，代价为 sum(cost2[0..j-1])，即 dp[0][j] = dp[0][j-1] + cost2[j-1]。
• 当 j = 0 但 i > 0 时，word2 是空字符串，必须删除 word1 的所有前 i 个字符，代价为 sum(cost1[0..i-1])，即 dp[i][0] = dp[i-1][0] + cost1[i-1]。

步骤 5：计算顺序
从 i = 0 到 len(word1)，j = 0 到 len(word2)，从小到大计算 dp[i][j]。最终答案为 dp[m][n]，其中 m = len(word1), n = len(word2)。

步骤 6：示例演算
以示例数据演算：

word1 = "sea", cost1 = [1,2,3]
word2 = "eat", cost2 = [4,5,6]
m=3, n=3
初始化 dp[0][0]=0
dp[0][1] = dp[0][0] + cost2[0] = 0+4=4
dp[0][2] = dp[0][1] + cost2[1] = 4+5=9
dp[0][3] = dp[0][2] + cost2[2] = 9+6=15
dp[1][0] = dp[0][0] + cost1[0] = 0+1=1
dp[2][0] = dp[1][0] + cost1[1] = 1+2=3
dp[3][0] = dp[2][0] + cost1[2] = 3+3=6

现在计算 dp[1][1]：word1[0]='s', word2[0]='e'，不同。
选择1：删除 's'，代价 1 + dp[0][1]=4 → 5
选择2：删除 'e'，代价 4 + dp[1][0]=1 → 5
所以 dp[1][1]=5
dp[1][2]：'s' vs 'a'，不同。
选择1：删除 's'，代价 1 + dp[0][2]=9 → 10
选择2：删除 'a'，代价 5 + dp[1][1]=5 → 10
dp[1][2]=10
dp[1][3]：'s' vs 't'，不同。
选择1：删除 's'，1 + dp[0][3]=15 → 16
选择2：删除 't'，6 + dp[1][2]=10 → 16
dp[1][3]=16
dp[2][1]：'e' vs 'e'，相同！dp[2][1]=dp[1][0]=1
dp[2][2]：'e' vs 'a'，不同。
选择1：删除 'e'（word1），代价 2 + dp[1][2]=10 → 12
选择2：删除 'a'（word2），代价 5 + dp[2][1]=1 → 6
dp[2][2]=6
dp[2][3]：'e' vs 't'，不同。
选择1：删除 'e'，2 + dp[1][3]=16 → 18
选择2：删除 't'，6 + dp[2][2]=6 → 12
dp[2][3]=12
dp[3][1]：'a' vs 'e'，不同。
选择1：删除 'a'，3 + dp[2][1]=1 → 4
选择2：删除 'e'，4 + dp[3][0]=6 → 10
dp[3][1]=4
dp[3][2]：'a' vs 'a'，相同！dp[3][2]=dp[2][1]=1
dp[3][3]：'a' vs 't'，不同。
选择1：删除 'a'，3 + dp[2][3]=12 → 15
选择2：删除 't'，6 + dp[3][2]=1 → 7
所以 dp[3][3]=7，与示例输出一致。

步骤 7：复杂度分析
时间复杂度：O(m×n)，需要填充 (m+1)×(n+1) 的 dp 表。
空间复杂度：可以优化到 O(min(m,n))，但为了清晰，通常用 O(m×n)。

步骤 8：关键点

• 这个动态规划本质上是求带权重的最长公共子序列的“保留最大代价”版本，但直接按删除代价定义状态更直观。
• 如果所有删除代价为 1，则退化为标准的最小删除距离问题。
• 该算法同样适用于字符代价不同的场景，如不同字符有不同的删除代价。