2

我对动态编程的问题有疑问。

给定两个字符串 A 和 B 找到两者中最短的交错字符串。

例如对于A = "APPLE",B = "ABSOLUTE"

最短的答案将是"ABPPSOLUTE" 代替回答我的函数返回"APPABSOLUTE"

我解决这个问题的想法是不断地交错 A[0] 和 B[0] len(A)+len(B)但这没有用。

4

1 回答 1

4

这里有一些想法可以帮助您入门。

动态编程的标签 wiki 将其描述为：

动态规划是一种算法技术，用于有效地解决具有包含许多重叠子问题的递归结构的问题

所以首先，试着想办法递归地解决这个问题。问：“我怎样才能咬掉这个问题的一小部分并处理它，这样我剩下的就是这个问题的另一个例子”？

在这种情况下，“小块”将是单个字符，剩下的将是字符串中的剩余字符。将问题想象为“这两个字符串的字符的最短交错是什么，从字符串 A 的位置 X 和字符串 B 的位置 Y 开始”？最初调用它时，X 和 Y 为 0。

该问题的三个可能答案是：

  • 如果 X 不在 A 的末尾，则从字符串 A 中取出字符 A[X]，然后对 X+1,Y 递归求解问题（找到从 X+1,Y 开始的两个字符串的最短交错）
  • 如上所述，但从字符串 B 而不是 A 中取出一个字符并递归求解 X,Y+1
  • 在A[X]和B[Y]的字符相同的情况下，去掉两者的字符，求X+1,Y+1的解

如果 X 和 Y 已经到达 A 和 B 的末尾，则返回一个空字符串。

返回上述 3 中最短的字符串，添加到您取出的 A 或 B（或两者）中的字符。

当函数从顶层返回时，您应该得到答案。

这就是“递归”部分。“重叠子问题”是关于如何重用已经计算过的东西。在这种情况下，您可以创建一个二维字符串数组，表示为 X 和 Y 的所有可能值解决的问题，并且在输入函数时，检查您是否已经有了答案，如果有就返回它。如果不是，则按上述方法计算，然后在从函数返回之前，将要返回的值保存在位置 [X][Y] 的数组中。

于 2016-06-06T06:35:58.427 回答