带权重的字符串交织问题（加权交织）

字数 3202 2025-12-08 17:38:47

带权重的字符串交织问题（加权交织）

题目描述
给定三个字符串 A、B 和 C，以及一个权重函数 w(char)，返回将 A 和 B 交织成 C 的最小总权重，如果无法交织则返回 -1。
交织是指保持 A 和 B 中字符的相对顺序，将它们交错合并成一个新字符串。
每次从 A 或 B 的头部取一个字符放到 C 中，该字符的权重为 w(char)，最终 C 的长度等于 A 和 B 的长度之和。
我们需要找到所有可能交织方式中，使用的字符权重之和最小的那一个。

示例
输入：
A = "ab"
B = "bc"
C = "abbc"
w('a') = 1, w('b') = 2, w('c') = 3

输出：8
解释：交织方式为：取 A[0]（'a', 权重1），再取 A[1]（'b', 权重2），再取 B[0]（'b', 权重2），再取 B[1]（'c', 权重3），总权重 = 1+2+2+3 = 8。
可以验证这是最小权重交织。

解题思路
这是一个区间动态规划（或序列DP）问题，其中“区间”由 A 和 B 的前缀长度定义。我们用 dp[i][j] 表示用 A 的前 i 个字符和 B 的前 j 个字符，交织成 C 的前 i+j 个字符时的最小总权重。
目标：dp[len(A)][len(B)]。

状态转移
考虑 C 的第 i+j 个字符（即 C[i+j-1]），它只能来自 A[i-1] 或 B[j-1]（如果存在且匹配）。

如果 i>0 且 A[i-1] == C[i+j-1]，则可以从 dp[i-1][j] 转移过来，此时新增权重为 w(A[i-1])。
如果 j>0 且 B[j-1] == C[i+j-1]，则可以从 dp[i][j-1] 转移过来，此时新增权重为 w(B[j-1])。
取两种情况的最小值（如果两种情况都可行）。

边界条件

dp[0][0] = 0：用空串交织得到空串，权重为0。
如果 A 的前 i 个字符正好匹配 C 的前 i 个字符，则 dp[i][0] = dp[i-1][0] + w(A[i-1])，否则为无穷大（表示不可能）。同理处理 dp[0][j]。

初始化技巧
为了方便，我们将 dp 初始化为一个很大的数（如 inf），然后从 dp[0][0] 开始递推。只有当匹配时才更新。

逐步求解

步骤1：定义状态
设 m = len(A), n = len(B)。
dp[i][j]：用 A 的前 i 个字符和 B 的前 j 个字符交织成 C 的前 i+j 个字符的最小权重。
注意：i 和 j 分别表示从 A 和 B 中取出的字符个数，所以 i 范围 [0, m]，j 范围 [0, n]。

步骤2：初始化
创建二维数组 dp，大小为 (m+1) x (n+1)，初始值为 inf。
dp[0][0] = 0。

步骤3：填充边界

当 j=0 时，只能从 A 取字符：
对于 i 从 1 到 m，如果 A[i-1] == C[i-1] 且 dp[i-1][0] 不是 inf，则 dp[i][0] = dp[i-1][0] + w(A[i-1])，否则保持 inf。
当 i=0 时，只能从 B 取字符：
对于 j 从 1 到 n，如果 B[j-1] == C[j-1] 且 dp[0][j-1] 不是 inf，则 dp[0][j] = dp[0][j-1] + w(B[j-1])，否则保持 inf。

步骤4：状态转移
对于 i 从 1 到 m，j 从 1 到 n：

检查是否可以从 A 取字符：如果 A[i-1] == C[i+j-1] 且 dp[i-1][j] != inf，则候选权重 = dp[i-1][j] + w(A[i-1])。
检查是否可以从 B 取字符：如果 B[j-1] == C[i+j-1] 且 dp[i][j-1] != inf，则候选权重 = dp[i][j-1] + w(B[j-1])。
取两者中的较小值作为 dp[i][j]（如果两者都不可行，则保持 inf）。

步骤5：获取结果
最终答案为 dp[m][n]。如果它为 inf，则返回 -1，否则返回该值。

复杂度分析

时间复杂度：O(m * n)，因为要填充一个 (m+1) x (n+1) 的 DP 表。
空间复杂度：O(m * n)，可以用滚动数组优化到 O(min(m, n))，但这里为了清晰先不优化。

示例推导
用上面的例子走一遍：
A = "ab", B = "bc", C = "abbc"
权重：w('a')=1, w('b')=2, w('c')=3

初始化 dp[3][3]（m=2, n=2，但dp下标到m和n），初始全 inf，dp[0][0]=0。

边界：

i>0, j=0:
i=1: A[0]='a', C[0]='a' 匹配，dp[1][0] = dp[0][0]+1 = 1。
i=2: A[1]='b', C[1]='b' 匹配，dp[2][0] = dp[1][0]+2 = 3。
i=0, j>0:
j=1: B[0]='b', C[0]='a' 不匹配 → dp[0][1]=inf。
j=2: 需要dp[0][1]不是inf才能继续，所以dp[0][2]=inf。

转移：
i=1, j=1: C[1]='b'（下标从0，所以i+j-1=1）
来自A: A[0]='a' != 'b' → 不可行。
来自B: B[0]='b' == 'b' 且 dp[1][0]=1 不是 inf → 候选 = 1+2=3。
所以 dp[1][1] = 3。

i=1, j=2: C[2]='b'
来自A: A[0]='a' != 'b' → 不可行。
来自B: B[1]='c' != 'b' → 不可行。
所以 dp[1][2] = inf。

i=2, j=1: C[2]='b'
来自A: A[1]='b' == 'b' 且 dp[1][1]=3 不是 inf → 候选 = 3+2=5。
来自B: B[0]='b' == 'b' 且 dp[2][0]=3 不是 inf → 候选 = 3+2=5。
取 min(5,5)=5 → dp[2][1] = 5。

i=2, j=2: C[3]='c'
来自A: A[1]='b' != 'c' → 不可行。
来自B: B[1]='c' == 'c' 且 dp[2][1]=5 不是 inf → 候选 = 5+3=8。
所以 dp[2][2] = 8。

结果：dp[2][2] = 8，与示例一致。

关键点总结

状态定义为“用A的前i个和B的前j个匹配C的前i+j个”，这是字符串交织问题的经典定义。
每次转移只取决于最后一个字符的来源（A或B），且必须与C对应位置匹配。
权重是累加的，所以转移时加上当前字符的权重。
如果最终状态不可达（值为inf），返回-1。

这个解法清晰展示了区间/序列DP在字符串交织问题上的应用，并且引入了权重优化，使得问题更具一般性。

带权重的字符串交织问题（加权交织）题目描述给定三个字符串 A 、 B 和 C ，以及一个权重函数 w(char) ，返回将 A 和 B 交织成 C 的最小总权重，如果无法交织则返回 -1 。交织是指保持 A 和 B 中字符的相对顺序，将它们交错合并成一个新字符串。每次从 A 或 B 的头部取一个字符放到 C 中，该字符的权重为 w(char) ，最终 C 的长度等于 A 和 B 的长度之和。我们需要找到所有可能交织方式中，使用的字符权重之和最小的那一个。示例输入： A = "ab" B = "bc" C = "abbc" w('a') = 1, w('b') = 2, w('c') = 3 输出：8 解释：交织方式为：取 A[ 0]（'a', 权重1），再取 A[ 1]（'b', 权重2），再取 B[ 0]（'b', 权重2），再取 B[ 1 ]（'c', 权重3），总权重 = 1+2+2+3 = 8。可以验证这是最小权重交织。解题思路这是一个区间动态规划（或序列DP）问题，其中“区间”由 A 和 B 的前缀长度定义。我们用 dp[i][j] 表示用 A 的前 i 个字符和 B 的前 j 个字符，交织成 C 的前 i+j 个字符时的最小总权重。目标： dp[len(A)][len(B)] 。状态转移考虑 C 的第 i+j 个字符（即 C[i+j-1] ），它只能来自 A[i-1] 或 B[j-1] （如果存在且匹配）。如果 i>0 且 A[i-1] == C[i+j-1] ，则可以从 dp[i-1][j] 转移过来，此时新增权重为 w(A[i-1]) 。如果 j>0 且 B[j-1] == C[i+j-1] ，则可以从 dp[i][j-1] 转移过来，此时新增权重为 w(B[j-1]) 。取两种情况的最小值（如果两种情况都可行）。边界条件 dp[0][0] = 0 ：用空串交织得到空串，权重为0。如果 A 的前 i 个字符正好匹配 C 的前 i 个字符，则 dp[i][0] = dp[i-1][0] + w(A[i-1]) ，否则为无穷大（表示不可能）。同理处理 dp[0][j] 。初始化技巧为了方便，我们将 dp 初始化为一个很大的数（如 inf ），然后从 dp[0][0] 开始递推。只有当匹配时才更新。逐步求解步骤1：定义状态设 m = len(A) , n = len(B) 。 dp[i][j] ：用 A 的前 i 个字符和 B 的前 j 个字符交织成 C 的前 i+j 个字符的最小权重。注意： i 和 j 分别表示从 A 和 B 中取出的字符个数，所以 i 范围 [0, m] ， j 范围 [0, n] 。步骤2：初始化创建二维数组 dp ，大小为 (m+1) x (n+1) ，初始值为 inf 。 dp[0][0] = 0 。步骤3：填充边界当 j=0 时，只能从 A 取字符：对于 i 从 1 到 m ，如果 A[i-1] == C[i-1] 且 dp[i-1][0] 不是 inf ，则 dp[i][0] = dp[i-1][0] + w(A[i-1]) ，否则保持 inf 。当 i=0 时，只能从 B 取字符：对于 j 从 1 到 n ，如果 B[j-1] == C[j-1] 且 dp[0][j-1] 不是 inf ，则 dp[0][j] = dp[0][j-1] + w(B[j-1]) ，否则保持 inf 。步骤4：状态转移对于 i 从 1 到 m ， j 从 1 到 n ：检查是否可以从 A 取字符：如果 A[i-1] == C[i+j-1] 且 dp[i-1][j] != inf ，则候选权重 = dp[i-1][j] + w(A[i-1]) 。检查是否可以从 B 取字符：如果 B[j-1] == C[i+j-1] 且 dp[i][j-1] != inf ，则候选权重 = dp[i][j-1] + w(B[j-1]) 。取两者中的较小值作为 dp[i][j] （如果两者都不可行，则保持 inf ）。步骤5：获取结果最终答案为 dp[m][n] 。如果它为 inf ，则返回 -1 ，否则返回该值。复杂度分析时间复杂度：O(m * n)，因为要填充一个 (m+1) x (n+1) 的 DP 表。空间复杂度：O(m * n)，可以用滚动数组优化到 O(min(m, n))，但这里为了清晰先不优化。示例推导用上面的例子走一遍： A = "ab", B = "bc", C = "abbc" 权重：w('a')=1, w('b')=2, w('c')=3 初始化 dp[ 3][ 3]（m=2, n=2，但dp下标到m和n），初始全 inf，dp[ 0][ 0 ]=0。边界： i>0, j=0: i=1: A[ 0]='a', C[ 0]='a' 匹配，dp[ 1][ 0] = dp[ 0][ 0 ]+1 = 1。 i=2: A[ 1]='b', C[ 1]='b' 匹配，dp[ 2][ 0] = dp[ 1][ 0 ]+2 = 3。 i=0, j>0: j=1: B[ 0]='b', C[ 0]='a' 不匹配 → dp[ 0][ 1 ]=inf。 j=2: 需要dp[ 0][ 1]不是inf才能继续，所以dp[ 0][ 2 ]=inf。转移： i=1, j=1: C[ 1 ]='b'（下标从0，所以i+j-1=1）来自A: A[ 0]='a' != 'b' → 不可行。来自B: B[ 0]='b' == 'b' 且 dp[ 1][ 0 ]=1 不是 inf → 候选 = 1+2=3。所以 dp[ 1][ 1 ] = 3。 i=1, j=2: C[ 2 ]='b' 来自A: A[ 0]='a' != 'b' → 不可行。来自B: B[ 1]='c' != 'b' → 不可行。所以 dp[ 1][ 2 ] = inf。 i=2, j=1: C[ 2 ]='b' 来自A: A[ 1]='b' == 'b' 且 dp[ 1][ 1 ]=3 不是 inf → 候选 = 3+2=5。来自B: B[ 0]='b' == 'b' 且 dp[ 2][ 0 ]=3 不是 inf → 候选 = 3+2=5。取 min(5,5)=5 → dp[ 2][ 1 ] = 5。 i=2, j=2: C[ 3 ]='c' 来自A: A[ 1]='b' != 'c' → 不可行。来自B: B[ 1]='c' == 'c' 且 dp[ 2][ 1 ]=5 不是 inf → 候选 = 5+3=8。所以 dp[ 2][ 2 ] = 8。结果：dp[ 2][ 2 ] = 8，与示例一致。关键点总结状态定义为“用A的前i个和B的前j个匹配C的前i+j个”，这是字符串交织问题的经典定义。每次转移只取决于最后一个字符的来源（A或B），且必须与C对应位置匹配。权重是累加的，所以转移时加上当前字符的权重。如果最终状态不可达（值为inf），返回-1。这个解法清晰展示了区间/序列DP在字符串交织问题上的应用，并且引入了权重优化，使得问题更具一般性。