algorithm - 动态规划-基本算法

Question

考虑以下问题:

我们有两个 cargo 装载序列，其中可以包含 Cereal 或牛。现在，我们还有一系列 cargo 装载，我们希望从初始序列中获得。

初始序列可能如下所示，我们想要实现的序列显示在右侧:

C   G                     
G   C                     
C   G                     G
C   C                     C
G   G                     G
 \ /
  ?

现在，在 ? 位置，您可以挑选左边的 cargo 或右边的 cargo 。应该进行挑选以匹配所需的最终序列。

比如我们要在开头选择Grain，那么图片就会变成这样:

    G                     
C   C                     
G   G                     G
С   C                     C
С   G                     G
 \ /
  ?  ---> G (we took it from the left)

---

那么，这个问题有一个众所周知的名字吗？我意识到这可以通过一个简单的动态规划算法来解决，但我想知道更多。

基本上，如果关于这个问题有更多的东西要读，我想读一下。 例如，如果我们有无限数量的有限输入序列，我对算法的复杂性一无所知。

Answer 1

我没有太多的见解可以分享，但这里是:

• 我们将 cargo 称为 0 和 1，而不是 C 和 G，此外，我们将两个队列标记为 0 和 1，而不是右和左。

• 首先，该算法无法通过无限(流式)输入序列求解。如果两个输入序列在“流式可见性窗口”之外只有 0 然后是 1，如果您的结果序列需要它，您不能瞄准这个 1，所以您可能会被卡住，而有一个答案。

• 既然我们不能谈论无穷大，那么让我们来分析一下求解器的复杂性。我看不出比你的算法好多少......如果结果序列的长度为 m，并且我们将结果建模为 0 和 1(左右)的序列，则有 2^m 种可能的解决方案。如果我们考虑在每一步，平均只有二分之一的机会只有一个输入序列有效，这意味着另一个序列以及其他后续序列将无效。这应该会导致复杂度为 O(m!)。