使用动态规划找到 A 和 B 的最短交错字符串
Find the shortest interleaved string of A and B with Dynamic Programming
我有一个关于动态规划的问题。
给定两个字符串 A 和 B，找到两者中最短的交错字符串。
例如 A = "APPLE"、B = "ABSOLUTE"
最短的答案是 "ABPPSOLUTE"
而是回答我的函数 returns "APPABSOLUTE"
我解决这个问题的想法是连续 len(A)+len(B) 次交错 A[0] 和 B[0]
但这没有用。
这里有一些想法可以帮助您入门。
动态规划的标签 wiki 将其描述为：
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems
所以先想办法递归解决这个问题。问："How can I bite off a small piece of this problem and process it, in such a way that what I have left over is another example of the problem"?
在这种情况下，"small piece" 将是单个字符，剩下的将是字符串中的剩余字符。把问题想成"what's the shortest interleaving of the characters of these two strings, starting at position X of string A and position Y of string B"？最初调用时，X 和 Y 为 0。
该问题的三个可能答案是：
- 如果X不在A的末尾，从字符串A中取出字符A[X]，然后递归求解for for X+1,Y（求从X开始的两个字符串的最短交错） +1,Y)
- 同上但从字符串 B 中取出一个字符而不是 A 并递归求解 X,Y+1
- 在A[X]和B[Y]的字符相同的情况下，把两者都去掉，求X+1,Y+1的解
如果 X 和 Y 已经到达 A 和 B 的末尾，return 一个空字符串。
Return 上述 3 个中最短的字符串，添加到您从 A 或 B（或两者）中删除的字符。
当顶层的函数 return 出现时，您应该有答案了。
那是 "recursive" 部分。 "overlapping subproblems" 是关于如何重用已经计算好的东西。在这种情况下，您可以制作一个二维字符串数组，表示针对 X 和 Y 的所有可能值解决的问题，并在输入函数时检查您是否已经有了答案，如果您知道答案，只需 return做。如果不是，那么按照上面的方法计算，在从函数 returning 之前，将您要 return 的值保存在数组中的 [X][Y].
位置
我有一个关于动态规划的问题。
给定两个字符串 A 和 B，找到两者中最短的交错字符串。
例如 A = "APPLE"、B = "ABSOLUTE"
最短的答案是 "ABPPSOLUTE"
而是回答我的函数 returns "APPABSOLUTE"
我解决这个问题的想法是连续 len(A)+len(B) 次交错 A[0] 和 B[0]
但这没有用。
这里有一些想法可以帮助您入门。
动态规划的标签 wiki 将其描述为：
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems
所以先想办法递归解决这个问题。问："How can I bite off a small piece of this problem and process it, in such a way that what I have left over is another example of the problem"?
在这种情况下，"small piece" 将是单个字符，剩下的将是字符串中的剩余字符。把问题想成"what's the shortest interleaving of the characters of these two strings, starting at position X of string A and position Y of string B"？最初调用时，X 和 Y 为 0。
该问题的三个可能答案是：
- 如果X不在A的末尾，从字符串A中取出字符A[X]，然后递归求解for for X+1,Y（求从X开始的两个字符串的最短交错） +1,Y)
- 同上但从字符串 B 中取出一个字符而不是 A 并递归求解 X,Y+1
- 在A[X]和B[Y]的字符相同的情况下，把两者都去掉，求X+1,Y+1的解
如果 X 和 Y 已经到达 A 和 B 的末尾，return 一个空字符串。
Return 上述 3 个中最短的字符串，添加到您从 A 或 B（或两者）中删除的字符。
当顶层的函数 return 出现时，您应该有答案了。
那是 "recursive" 部分。 "overlapping subproblems" 是关于如何重用已经计算好的东西。在这种情况下，您可以制作一个二维字符串数组，表示针对 X 和 Y 的所有可能值解决的问题，并在输入函数时检查您是否已经有了答案，如果您知道答案，只需 return做。如果不是，那么按照上面的方法计算，在从函数 returning 之前，将您要 return 的值保存在数组中的 [X][Y].
位置