Python中的动态规划算法

动态规划 (DP) 是一种解决计算和数学问题的算法技术，通过将其分解为更小、重叠的子问题来实现。DP 对于优化问题非常有效，当你需要在众多可能的选项中找到最优答案时，例如发现最短路径、最大化/最小化某个值或计算组合数。通过只解决每个子问题一次并保存答案，DP 有助于最大限度地减少重复计算，使过程更有效。

我们在哪里使用动态规划算法？

1. 最优子结构

如果一个问题的最优解可以由其子问题的最优解构造而成，则该问题就具有最优子结构性质。动态规划利用最优子结构原理，这意味着一个问题的最佳解决方案可以从其子问题的最佳解决方案获得。

2. 重叠子问题

子问题是单独完成的任务，而重叠子问题涉及多次重复相同的任务。

动态规划存储重叠子问题的解，以避免冗余计算。

动态规划是一种解决问题的技术，它涉及到将复杂问题分解为更小的子问题，而这些子问题又可以进一步分解为更小的组件。这些子问题是重叠的，并且依赖于先前计算的值。动态规划会存储这些计算出的值，从而减少了重复计算的需要，从而节省了大量时间并提高了解决方案的速度。

动态规划方法

1. 自顶向下方法
2. 自底向上方法

自顶向下 (记忆化)

在自顶向下方法中，您从主问题开始，然后将其分解为更小的子问题。通常会使用递归来解决这些子问题，并将它们的结果存储在缓存中以防止重复计算。每当重新遇到一个子问题时，就会从缓存中检索其先前计算的结果。这种方法通常被称为“记忆化”。

优点

记忆化存储并重用先前计算的子问题的结果，以避免冗余计算，从而显着提高性能。

易于实现：实现自顶向下的动态规划解决方案可能比自底向上的方法更简单。在后者中，需要管理用于子问题结果的表或数组。

降低复杂度：自顶向下方法通过避免用于子问题的嵌套循环或复杂索引来简化代码结构，从而得到更优雅的解决方案。

清晰度和可读性：在使用自顶向下动态规划解决问题时，问题的递归结构通常会被紧密地反映出来。因此，代码更直观且易于理解，因为它直接代表了问题分解为子问题的过程。

缺点

在自顶向下方法中使用递归时，额外的函数调用可能会引入开销，并且执行速度比使用迭代的自底向上方法慢。高度嵌套的递归调用可能导致严重的性能问题。

自顶向下方法是递归的，在跟踪已解决的子问题和记忆化的结果方面可能会遇到困难。这可能会导致调试复杂化，并使跟踪子问题状态具有挑战性。

自底向上 (制表)

解决问题的自底向上方法包括先解决最小的子问题（基本情况），然后逐步构建以解决主问题。此方法不使用递归，而是使用循环来计算子问题的结果并将其存储在数组或表中。此技术也称为“制表”。

优点

可预测的空间复杂度：自底向上方法明确为存储子问题结果的表或数组分配内存，从而可以轻松预测和控制空间复杂度。这种方法更适合内存限制已知的问题。

并行性：自底向上动态规划促进了并行性，允许同时或有序地解决子问题，从而利用多个处理器或线程来加速解决方案。

无递归开销：与自顶向下方法相比，自底向上方法避免了函数调用和递归开销，从而提高了执行速度并减少了内存消耗，尤其对于递归深度大的问题。

缺点

在处理动态规划问题时，定义基本情况和表的初始化可能很棘手，尤其是在基本情况不明显的情况下。

在解决子问题时，自底向上动态规划通常需要比自顶向下方法更复杂的代码，这可能导致代码可读性降低。

当处理具有更自然递归结构的问题时，自顶向下方法可能比自底向上动态规划更灵活。后者不允许选择性计算或递归树中的分支。

与普通方法和自顶向下方法的比较

让我们看一个简单的程序，它使用自顶向下方法和普通递归方法打印第 n 个斐波那契值。

自顶向下方法

程序

输出

The 10th Fibonacci number is: 55

递归方法

程序

输出

The 10th Fibonacci number is: 55

两种方法的解释

为了获得更好的时间复杂度，通常推荐使用记忆化实现的自顶向下动态规划方法，而不是朴素的递归方法。这是因为带有记忆化的自顶向下动态规划会存储并重用先前已解决子问题的解，从而避免了不必要的计算。

递归方法

指数时间复杂度 (O(2^n))。

自顶向下 (带记忆化)

时间复杂度：O(n) 或 O(n log n)（线性或对数线性）

因此，为了优化计算斐波那契数的时间复杂度，带有记忆化的自顶向下动态规划方法是更优的选择。

动态规划算法

Dijkstra 算法

Dijkstra 算法是一种在图中查找节点之间最短路径的方法。它通过选择距离起始节点最近的节点，然后继续选择下一个最近的节点，直到到达目的地。这种方法基于在每个步骤中选择最佳解决方案的原则，这也称为贪婪算法。当所有边权重都为非负时，它效果很好。

相比之下，动态规划会考虑所有可能的解决方案，并选择能带来最佳整体结果的方案。它通过探索所有可能的路径并跟踪迄今为止找到的最佳解决方案来实现此目的。这种方法更耗时，但可以保证找到最优解决方案。

Bellman-Ford 算法

Bellman-Ford 算法是计算机科学和图论中一个著名的算法，用于查找加权有向图中源顶点到所有其他顶点的最短路径。它可以处理具有负权重边的图，并且可以检测负权重圈，使其成为各种应用的最佳选择。

在 Bellman-Ford 算法的上下文中，它使用动态规划通过迭代松弛边来确定从源顶点到所有其他顶点的最短距离。该算法使用动态规划来确保它检查图中的所有可能路径，从而使其能够处理具有负权重边的图并识别负权重圈。这种迭代和基于松弛的策略使该算法能够有效地计算各种场景下的最短路径。

最大子数组和 (Kadane's Algorithm)

Kadane 算法是一种广泛使用且高效的技术，可帮助查找一维数字数组中子数组的最大和。它在寻找最大子数组和等问题中特别有用，例如最大子数组和或相关问题，如最大子序列和。该算法对于正数和负数都有效。它的时间复杂度为 O(n)，使其非常高效。

Kadane 算法是一种动态规划算法，它专门且高效地查找最大子数组和。它利用动态规划的原理来维护数组中每个位置结尾的最大子数组和以及迄今为止找到的最大子数组和。通过迭代更新这些值，它可以在不重新评估相同子问题多次的情况下找到最大子数组和。

背包问题

背包问题是计算机科学和数学领域中一个著名的优化问题。在此问题中，您会得到一组具有相应重量和价值的物品，以及一个具有最大重量容量的背包。主要目标是在不超出背包容量的情况下，选择一组物品以最大化总价值。这个问题通常被称为 0/1 背包问题，因为对于每个物品，您有两个选择：要么将其放入背包（0），要么将其排除（1）。

在解决背包问题时，我们经常会遇到相同的子问题多次。例如，我们需要知道使用容量为 W 的背包和前 k 个物品的子集可获得的最大价值。这些重叠的子问题由动态规划解决，它将结果存储在表或数组中。通过重用这些结果，我们可以避免冗余计算并提高效率。

0/1 背包问题

一个经典的优化问题，称为“背包问题”，旨在在控制其总重量的情况下最大化一组商品的总体价值。

在 0/1 背包问题中，您不能只取一部分物品，因为每个物品都可以被放入背包或从背包中移除。

这里有一个简单的程序，它使用动态规划来演示 0/1 背包问题。

程序

输出

Maximum value in 0/1 Knapsack: 220

说明

提供的 0/1 背包问题的 Python 程序结合了动态规划，通过将其分解为更小的子问题并将它们的解存储在表中来高效地解决它。

设置表 (dp)

该程序初始化一个名为 dp 的表，其维度为 (n + 1) x (capacity + 1)，其中 n 是物品数量，capacity 是背包的最大容量。

使用前 i 个物品和容量为 w 的背包可以达到的最高价值由符号 dp[i][w] 表示。

自底向上填充表 (dp)

然后，程序使用自底向上方法填充表。内循环遍历背包的潜在容量 (w)，而外循环遍历物品 (i)。

对于每个单元格 dp[i][w]，程序考虑两种可能性

• 包含当前物品（weights[i-1] <= w）。将当前物品的价值添加到不含当前物品且容量减小的最大价值（dp[i-1][w-weights[i-1]]）中。
• 使用不含当前物品的最大价值（dp[i-1][w]）来排除当前物品。

最终结果来自表的右下角单元格 (dp[n][capacity])

Floyd-Warshall 算法

Floyd-Warshall 算法是一种强大的动态规划算法，用于查找加权边有向图中所有顶点对之间的最短路径。该算法能够处理具有正负边权重的图，甚至可以处理带有负权重圈的图。

要使用 Floyd-Warshall 算法确定顶点 i 和 j 之间的最短路径，我们需要考虑顶点 i 和所有其他顶点 k 之间的最短路径，以及 k 和 j 之间的最短路径。该算法通过迭代地考虑所有可能的中间顶点 k 来帮助我们找到所有顶点对之间的最短路径。

Floyd-Warshall 算法使用动态规划来查找图中所有顶点对之间的最短路径。它通过考虑所有可能的中间顶点并计算递增数量的最短路径来实现。这个过程建立在先前计算的子问题解的基础上，从直接边开始。这种算法的迭代性质使其成为解决复杂图问题的强大工具。

结论

动态规划是一种高度通用且必不可少的问题解决技术，在算法设计和优化中发挥着重要作用。它是一种强大的工具，可以通过将大问题分解为更小、更易于管理子问题来有效地识别最优解决方案。学习和掌握动态规划对于任何程序员或数学家来说都是一项宝贵的技能，因为它能帮助他们更高效、更有效地解决挑战性问题。总之，动态规划是一个值得学习和掌握的重要概念。