本文与生产开发无关，但涉及编程。我将讨论动态规划（DP）以及如何有效地利用以前的计算经验。我希望你会觉得它很有趣。 动态规划简介 动态规划一词最早由美国著名数学家、计算机技术领域的顶尖专家之一理查德·贝尔曼 (Richard Bellman) 在 20 世纪 50 年代首次 。动态规划（DP）是一种通过将复杂任务分解为更小的子问题来解决复杂任务的方法。  使用  DP能够解决的问题类型必须满足两个标准：   。动态规划意味着较小的子问题的解决方案可以用来解决初始问题。最优子结构是“分而治之”范式的主要特征。 1. 最优子结构 一个经典的实现示例是合并排序算法，在该算法中，我们递归地将问题分解为最简单的子问题（大小为 1 的数组），然后根据每个子问题进行计算。结果用于解决下一层（更大的子问题），直到实现初始层。   。在计算机科学中，如果一个问题可以分解为可重复使用多次的子问题，则该问题被称为具有重叠的子问题。换句话说，使用相同的输入数据运行相同的代码并得到相同的结果。这个问题的一个典型例子是斐波那契数列中第 N 个元素的计算，我们将在下面讨论。 2、子问题重叠 你可以说 DP 是使用分而治之范式的一个特例，或者是它的一个更复杂的版本。该模式非常适合解决涉及组合的任务，其中计算大量不同的组合，但元素的 N 数量通常是单调且相同的。 在最优子结构和重叠子问题中，如果采用蛮力方法，就会有大量的重复计算和运算。 DP 帮助我们优化解决方案，并通过使用两种主要方法来避免计算量加倍：记忆和制表：   是通过递归实现的。一个任务被分解为更小的子问题，它们的结果被输入内存并通过重复使用组合起来解决原始问题。 1. 记忆化（自上而下的方法） 此方法通过递归方法调用使用堆栈内存 缺点：  DP 任务的灵活性。 优点：   是使用迭代方法实现的。从最小到初始的子问题依次迭代计算。 2. 制表（自下而上的方法） 应用范围有限。这种方法需要对子问题的整个序列有初步的了解。但在某些问题上，这是不可行的。 缺点： 高效的内存使用，因为所有内容都在单个函数中运行。 优点： 这个理论可能听起来乏味且难以理解——让我们看一些例子。 问题：斐波那契数列 DP 的一个经典例子是计算斐波那契数列中的第 N 个元素，其中每个元素都是前两个元素的和，并且第一个和第二个元素等于 0 和 1。 根据假设，我们首先关注最优子结构的性质，因为为了计算一个值，我们需要找到前一个值。为了计算前一个值，我们需要找到之前的值，依此类推。重叠子任务的性质如下图所示。 对于此任务，我们将研究三种情况： 直接方法：有什么缺点？ 使用记忆的优化解决方案 使用表格的优化解决方案 直接/暴力方法 您可能首先想到的是输入递归，将前面的两个元素相加，并给出结果。   /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } } 在下面的屏幕上，您可以看到一堆函数调用，用于计算序列中的第五个元素。  请注意，函数 被调用了五次，   3 次。具有一个签名、具有相同参数的函数会被重复启动，并执行相同的操作。当N数增加时，树不是线性增长，而是指数增长，这会导致巨大的重复计算。 fib(1) fib(2) 数学分析：  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 增加，变化就会极大地升级，并且在我们的头脑中想象这些是不可能的。  这项任务可以归因于组合学。让我们弄清楚可以形成哪些组合，以及如何找到它们形成的模式。 每棵树都从顶部节点（树的顶点）开始。然后树的深度会扩展。 每个节点都是新子树（子树）的开始，如屏幕上所示。左子树为绿色，右子树为红色。每一个都有自己的顶点。  让我们看一个任务示例，其中概念级别的 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) 计算  。如果我们为该顶点分配一个节点，则还剩下 3 个节点。 numOfUniqueTrees(4) 分布 (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 .   = 14。 numOfUniqueTrees(4) 我们根据记忆的经验，将计算的结果输入到变量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，   = 42。 numOfUniqueTrees(5) 让我们回到 的计算，它等于分布之和。 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 的重叠子问题。在简单的解决方案中，  将被调用 18 次（如下屏幕）。随着 N 的增加，相同计算的重复次数将会大大增加。  numOfUniqueTrees(3) 我强调，(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 } } 结论 在某些情况下，通过动态规划来解决任务可以节省大量时间并使算法发挥最大效率。 感谢您阅读本文的最后。我很乐意回答您的问题。

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

inDrive.Tech

該音頻是用故事的原始語言製作的！

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

About Author

註釋

標籤

这篇文章刊登在

Related Stories

想赢得 HackerNoon 写作比赛吗？以下是 #crypto-api 比赛获奖者的推荐

Telegram：加密岛通往大陆的桥梁

数字游民请注意：您需要了解泰国新推出的 DTV 签证

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

想赢得 HackerNoon 写作比赛吗？以下是 #crypto-api 比赛获奖者的推荐

Telegram：加密岛通往大陆的桥梁

数字游民请注意：您需要了解泰国新推出的 DTV 签证

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps