了解动态规划以便有效地使用它

本文与生产开发无关，但涉及编程。我将讨论动态规划（DP）以及如何有效地利用以前的计算经验。我希望你会觉得它很有趣。

动态规划简介

动态规划一词最早由美国著名数学家、计算机技术领域的顶尖专家之一理查德·贝尔曼 (Richard Bellman) 在 20 世纪 50 年代首次使用。动态规划（DP）是一种通过将复杂任务分解为更小的子问题来解决复杂任务的方法。

DP能够解决的问题类型必须满足两个标准：

1. 最优子结构。动态规划意味着较小的子问题的解决方案可以用来解决初始问题。最优子结构是“分而治之”范式的主要特征。

一个经典的实现示例是合并排序算法，在该算法中，我们递归地将问题分解为最简单的子问题（大小为 1 的数组），然后根据每个子问题进行计算。结果用于解决下一层（更大的子问题），直到实现初始层。

2、子问题重叠。在计算机科学中，如果一个问题可以分解为可重复使用多次的子问题，则该问题被称为具有重叠的子问题。换句话说，使用相同的输入数据运行相同的代码并得到相同的结果。这个问题的一个典型例子是斐波那契数列中第 N 个元素的计算，我们将在下面讨论。

你可以说 DP 是使用分而治之范式的一个特例，或者是它的一个更复杂的版本。该模式非常适合解决涉及组合的任务，其中计算大量不同的组合，但元素的 N 数量通常是单调且相同的。

在最优子结构和重叠子问题中，如果采用蛮力方法，就会有大量的重复计算和运算。 DP 帮助我们优化解决方案，并通过使用两种主要方法来避免计算量加倍：记忆和制表：

1. 记忆化（自上而下的方法）是通过递归实现的。一个任务被分解为更小的子问题，它们的结果被输入内存并通过重复使用组合起来解决原始问题。

• 缺点：此方法通过递归方法调用使用堆栈内存
• 优点： DP 任务的灵活性。

2. 制表（自下而上的方法）是使用迭代方法实现的。从最小到初始的子问题依次迭代计算。

• 缺点：应用范围有限。这种方法需要对子问题的整个序列有初步的了解。但在某些问题上，这是不可行的。
• 优点：高效的内存使用，因为所有内容都在单个函数中运行。

这个理论可能听起来乏味且难以理解——让我们看一些例子。

问题：斐波那契数列

DP 的一个经典例子是计算斐波那契数列中的第 N 个元素，其中每个元素都是前两个元素的和，并且第一个和第二个元素等于 0 和 1。

根据假设，我们首先关注最优子结构的性质，因为为了计算一个值，我们需要找到前一个值。为了计算前一个值，我们需要找到之前的值，依此类推。重叠子任务的性质如下图所示。

对于此任务，我们将研究三种情况：

1. 直接方法：有什么缺点？
2. 使用记忆的优化解决方案
3. 使用表格的优化解决方案

直接/暴力方法

您可能首先想到的是输入递归，将前面的两个元素相加，并给出结果。

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

在下面的屏幕上，您可以看到一堆函数调用，用于计算序列中的第五个元素。

请注意，函数fib(1)被调用了五次， fib(2) 3 次。具有一个签名、具有相同参数的函数会被重复启动，并执行相同的操作。当N数增加时，树不是线性增长，而是指数增长，这会导致巨大的重复计算。

数学分析：

时间复杂度： O(2n)，

空间复杂度： O(n) -> 与递归树的最大深度成比例，因为这是隐式函数调用堆栈中可以存在的最大元素数。

结果：这种方法效率极低。例如，计算第30个元素需要1,073,741,824次运算。

记忆（自上而下的方法）

在这种方法中，除了内存分配之外，实现与前面的“暴力”解决方案没有太大不同。让它成为变量备忘录，我们在其中收集堆栈中任何已完成的 fib() 函数的计算结果。

应该注意的是，拥有一个整数数组并通过索引引用它就足够了，但是，为了概念清晰，创建了一个哈希映射。

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

让我们再次关注函数调用堆栈：

• 将结果写入备忘录的第一个完成的函数是突出显示的fib(2) 。它将控制权返回给突出显示的fib(3) 。
• 突出显示的fib(3)在对fib(2)和fib(1)调用的结果求和后找到其值，在备忘录中输入其解决方案并将控制权返回给fib(4) 。
• 我们已经达到了重用早期经验的阶段 - 当控制权返回到fib(4)时， fib(2)调用等待轮到它。 fib(2)反过来，而不是调用 ( fib(1) + fib(0) )，而是使用备忘录中的整个完成的解决方案，并立即返回它。
• fib(4)被计算并将控制权返回给fib(5) ，后者只需启动fib(3) 。在最后一个类比中， fib(3)立即从备忘录中返回一个值，而不进行计算。

我们可以观察到函数调用和计算的数量减少了。此外，当 N 增加时，减少量也会呈指数级减少。

数学分析：

时间复杂度：O(n)

空间复杂度：O(n)

结果：渐近复杂度存在明显差异。与原始解决方案相比，这种方法已将其减少为时间线性，并且没有增加内存。

制表（自下而上的方法）

如上所述，这种方法涉及从较小的子问题到较大的子问题的迭代计算。对于斐波那契数列，最小的“子问题”是序列中的第一个和第二个元素，分别为 0 和 1。

我们很清楚元素之间的相互关系，用公式表示： fib(n) = fib(n-1) + fib(n-2) 。因为我们知道前面的元素，所以我们可以轻松计算出下一个、之后的元素，依此类推。

通过总结我们知道的值，我们可以找到下一个元素。我们循环执行此操作，直到找到所需的值。

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

数学分析：

时间复杂度：O(n)

空间复杂度：O(1)

结果：这种方法在速度方面与记忆一样有效，但它占用的内存量是恒定的。

问题：独特的二叉树

让我们看一个更复杂的问题：我们需要找到可以从 N 个节点创建的所有结构唯一的二叉树的数量。

二叉树是一种分层数据结构，其中每个节点最多有两个后代。作为一般规则，第一个称为父节点，并且有两个子节点 - 左子节点和右子节点。

假设我们需要找到 N = 3 的解决方案。这三个节点有 5 棵结构独特的树。我们可以在头脑中数出它们，但如果 N 增加，变化就会极大地升级，并且在我们的头脑中想象这些是不可能的。

这项任务可以归因于组合学。让我们弄清楚可以形成哪些组合，以及如何找到它们形成的模式。

1. 每棵树都从顶部节点（树的顶点）开始。然后树的深度会扩展。
2. 每个节点都是新子树（子树）的开始，如屏幕上所示。左子树为绿色，右子树为红色。每一个都有自己的顶点。

让我们看一个任务示例，其中概念级别的 N = 6。我们将调用计算函数 numOfUniqueTrees(n: Int) 。

在我们的示例中，给出了 6 个节点，根据前面提到的原理，其中一个节点形成树的顶点，另外 5 个节点构成剩余节点。

从现在开始，我们与其余节点进行交互。这可以通过多种方式来完成。例如，使用所有五个节点形成左子树或将所有五个节点发送到右子树。或者通过将节点分为两部分 — 2 个在左侧，3 个在右侧（参见下面的屏幕），我们的此类变体数量有限。

为了获得结果numOfUniqueTrees(6) ，我们需要考虑分布节点的所有变体。它们如表所示：

该表显示了 6 种不同的节点分布。如果我们找到每个分布可以生成多少个独特的树并将其相加，我们将获得最终结果。

如何找到用于分配的独特树的数量？

我们有两个参数：左节点和右节点（表中的左列和右列）。

结果将等于： numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) 。

为什么？在左边，我们将有 X 棵独特的树，对于每棵树，我们将能够在右边放置 Y 种独特的树变体。我们将它们相乘即可得到结果。

让我们找出第一个分布的变体（左 5，右 0）

numOfUniqueTrees(5) * numOfUniqueTrees(0) ，因为右侧没有节点。结果是numOfUniqueTrees(5) — 左侧具有恒定右侧的唯一子树的数量。

计算numOfUniqueTrees(5) 。

现在我们有最小的子问题。我们将像对待更大的那样对待它。在这个阶段，DP任务的特征很明显——最优子结构、递归行为。

一个节点（绿色节点）被发送到该顶点。我们以类似于之前经验（4:0）、（3:1）、（2:2）、（1:3）、（0:4）的方式分配剩余（四个）节点。

我们计算第一个分布 (4:0)。通过前面的类比，它等于numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) 。

计算numOfUniqueTrees(4) 。如果我们为该顶点分配一个节点，则还剩下 3 个节点。

分布 (3:0)、(2:1)、(1:2)、(0:3)。

对于 2 个节点，只有两个唯一的二叉树，对于 1 — 一个。前面我们已经提到，三个节点的唯一二叉树有 5 种变体。

结果 — 分布 (3:0)、(0:3) 等于 5、(2:1)、(1:2) — 2。如果我们将 5 + 2 + 2 + 5 加起来，我们得到 14 . numOfUniqueTrees(4) = 14。

我们根据记忆的经验，将计算的结果输入到变量memo中。每当我们需要找到四个节点的变化时，我们不会再次计算它们，而是重用以前的经验。

让我们回到计算 (5:0)，它等于分布 (4:0)、(3:1)、(2:2)、(1:3)、(0:4) 的总和。我们知道 (4:0) = 14。让我们看一下备忘录，(3:1) = 5，(2:2) = 4（左侧 2 个变体 * 右侧 2 个变体），(1:3) = 5, (0:4) = 14。如果我们将这些相加，我们得到 42， numOfUniqueTrees(5) = 42。

让我们回到numOfUniqueTrees(6)的计算，它等于分布之和。

(5:0) = 42、(4:1) = 14、(3:2) =10（左 5 * 右 2）、(2:3) = 10、(1:4) = 14、(0: 5) = 42。如果我们将这些相加，我们得到 132， numOfUniqueTrees(5) = 132 。

任务解决了！

结果：让我们注意解决方案中 N = 6 的重叠子问题。在简单的解决方案中， numOfUniqueTrees(3)将被调用 18 次（如下屏幕）。随着 N 的增加，相同计算的重复次数将会大大增加。

我强调，(5 左，0 右) 和 (0 左，5 右) 的唯一树的数量将是相同的。仅在一种情况下它们位于左侧，而在另一种情况下位于右侧。这也适用于 (4 left, 1 right) 和 (1 left, 4 right)。

记忆化作为动态编程的一种方法，使我们能够针对如此复杂的任务优化解决方案。

执行

class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

结论

在某些情况下，通过动态规划来解决任务可以节省大量时间并使算法发挥最大效率。

感谢您阅读本文的最后。我很乐意回答您的问题。