algorithm - 动态规划 : Do I have overlapping sub-problems?

Question

我的算法

让我们假设我有一个二维实数数组。我从这个数组中的一个特定单元格开始，其中有一个特别大的数字。我想标记其他哪些单元格应该属于提到的起始单元格。规则是这样的:如果我找到从起始单元格走到另一个单元格的方法，则另一个单元格属于起始单元格。我只被允许上下走一个牢房。我只能从编号较大的牢房走到编号较小的牢房。这是我从中心 9 开始的示例

我的伪算法是

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

现在是第二个方面，我不仅对一个起始单元执行此操作，而且对多个起始单元执行此操作，例如

动态编程

我研究了 dynamic programming并发现需要满足两个条件才能应用动态规划:

• 子问题需要重叠
• 子问题需要有最优子结构

[动态规划]指的是通过以递归的方式将一个复杂的问题分解成更简单的子问题来简化[...]子问题的最优解，则称其具有最优子结构。[...] 为了使动态规划适用，问题必须具有两个关键属性:最优子结构和重叠子问题。如果一个问题可以通过组合非重叠子问题的最优解来解决，则该策略称为“分而治之”。这就是归并排序和快速排序不属于动态规划问题的原因。最优子结构意味着给定优化问题的解可以通过其子问题的最优解的组合来获得。这种最优子结构通常通过递归来描述。[...]重叠的子问题意味着子问题的空间必须很小，也就是说，任何解决问题的递归算法都应该一遍又一遍地解决相同的子问题，而不是产生新的子问题。” Wikipedia

我想知道我的算法是否是动态规划。它绝对是递归的，并且在子结构中似乎是最优的。不过，我开始怀疑重叠的子结构。有一个斐波那契数列的例子，但在我看来，关键方面是可以存储递归算法的中间结果。对于我的算法，不能存储中间结果——至少不能存储单个起始单元的一次运行。然而，当我考虑整个问题时，有许多起始单元，我们看到一些区域是连接的:

假设我们从左图中的橙色 9 开始，沿着绿色路径前进，直到到达蓝色 5。从那里我们也可以到达蓝色 3 和蓝色 2。我们完成了左侧的算法橙色 9.

现在我们转向右图中下方的橙色 8。我们从这个 8 开始，沿绿色路径向上到达绿色 6。从那里我们到达蓝色 5。我们已经从之前的计算(从左图中的橙色 9)中知道蓝色 3 和蓝色 2都是从蓝色 5 可达的，所以我们可以一举标记它们，而无需重新计算路径。

这就是为什么我认为我的整体问题可以用动态规划解决。

问题

1. 我的算法/问题是动态规划吗？为什么，为什么不呢？
2. 如果不是，我能否使其成为动态规划？如果是，如何实现？

Answer 1

是的，这当然是一个动态规划问题。它实际上是最简单/最基本的动态规划问题——在有向无环图中找到从起始节点可达的所有节点(在您的情况下为多个起始节点)。您可以使用深度优先搜索或广度优先搜索来解决它。

它符合这样的定义:

最佳结构？是的，我可以从单元格 x 到达的单元格是 x 加上我可以从 x 的较小邻居到达的单元格的并集。

重叠的子问题？是的，x 的两个邻居可以共享同一个较小的邻居。

为了使您发布的算法成为动态规划算法，您只需要像这样记住子问题:

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr) AND cell_is_not_marked(neighborNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

请注意，这也会将您的算法从指数时间更改为线性时间，并且它是深度优先搜索