动态规划

在数学、计算机科学和经济学中，动态规划是指将一个复杂问题分解为几个简单问题来解决的方法，在短时间内求解时使用。

为了解决给定的问题，将问题分解为子问题，然后将子问题组合起来以达到最终的目标，计算出每个子问题的解后，将解保存起来，以便以后解决相同的子问题。这样，动态规划可以减少计算次数，当子问题的数量呈指数级增长时，这种方法特别有用。

动态规划算法用于最短路径问题、矩阵平方问题等的优化。这是因为动态规划会检查解决问题的所有方法并在其中找到最优解。如果处理得足够快，动态规划就可以可以说是一个最优解。

有时，只需将存储的序列（输入所有先前数据的序列）替换为简单的递归函数，就可以找到动态算法来找到最优解。但是，许多问题需要比这更复杂的编程。其中一些需要多个 在某些情况下，必须使用参数来编写递归函数，这样也存在无法创建动态算法的问题，此类谜题的代表例子是 EggDropping Puzzle。

如上所述，动态规划方法的缺点是要考虑所有可能的方法，为了克服这个缺点，贪心算法出现了，而不是动态规划方法。已经证明，贪心算法可以在许多问题中找到最优解，例如树问题）。

我们来比较一下贪心算法和动态规划方法。假设我们想在交通拥堵路段尽快找到从 A 点到 B 点的路线。如果我们在这个问题中使用动态规划，我们可以解决所有情况而交通则是考虑所有的交通拥堵情况来寻找最优路线，而贪心算法每时每刻看到路口都会搜索并找到最快的路线，而不考虑全局。

当然，由于我们在用动态规划寻找路线时，开车时要稍事休息，所以使用动态规划的缺点是需要花费一些时间，但这样得到的路线（假设交通环境没有改变） ）可以保证它是最快的路线。另一方面，贪心算法虽然立即有效，但并不总能找到最佳路线。即使找到了每个路段的最佳路线，也不一定能找到最佳路线。成为整体最优路线，换句话说，动态规划相对于贪心算法在时间上可能效率较低，但结果却可以获得高效值。

这是数学家理查德·贝尔曼在 20 世纪 40 年代使用的术语。1953 年，贝尔曼将这种方法命名为“动态规划”，用于解决较小问题嵌套在较大问题中的问题。

正如贝尔曼在他的自传《风暴之眼》中所说：

1950 年秋天，我在兰德公司工作。我在这里的第一个任务是为多阶段决策过程命名一个合适的术语。您想知道“动态规划”这个名字从何而来吗？对我来说，那是一个糟糕的工作时间数学。当时我们在华盛顿和一个叫威尔逊的人一起工作。威尔逊对研究有一种病态的恐惧。不幸的是，兰德公司是一家空军公司，而威尔逊是空军行政部门、国防部的负责人。委员会。所以当我在兰德时，我可以看到威尔逊和空军正在掩盖我在数学上的工作。当我第一次来时，我用“决策过程”这个名字来解决上述问题，但我遇到了麻烦这里使用“过程”这个词。我添加了“编程”这个词。另外，我想传达这样的想法：这个过程是多步骤的、时变的和“动态的”。所研究的算法的本质是准确的指出，况且威尔逊并没有受到伤害，空军在这句话中也抓不住吊舱，真正享受了一石二鸟的效果。

换句话说，“动态”一词是贝尔曼采用的术语，表示该算法的“时变和多步骤”特性。此外，“编程”一词在空军内部用于文字处理训练或这样创造出来的“动态规划”这个词就变成了代表一种编程技术的词，比如线性规划或者数学规划。

• 最长公共子序列 - 查找两个或多个给定序列的子序列的最长序列的算法
• Cocke-Younger-Kasami (CYK) 算法 - 一种算法，用于确定是否可以使用给定的上下文无关语法创建所需的字符串
• 维特比算法
• Earley 算法
• 贝尔曼-福特算法
• Dijkstra 算法 - 一种查找给定起点和其他点之间最短路径的算法
• Floyd-Warshall 算法
• 链矩阵乘法的最佳乘法顺序
• 子集算法
• 背包问题