Data Structures Algorithms 简明教程

Dynamic Programming

动态规划方法类似于分而治之，将问题分解为更小且更小的可能子问题。但与分而治之不同，这些子问题不是独立解决的。相反，这些较小子问题的结果会被记住并用于解决相似的或重叠的子问题。

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

通常，动态规划算法用于解决优化问题。在解决手头的子问题之前，动态算法将尝试检查以前已解决的子问题的结果。子问题的解会结合在一起以便获得最佳的最终解。因此，这种范式被称为使用自底向上的方法。

Mostly, dynamic programming algorithms are used for solving optimization problems. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best optimal final solution. This paradigm is thus said to be using Bottom-up approach.

所以我们可以得出以下结论：

So we can conclude that −

  1. The problem should be able to be divided into smaller overlapping sub-problem.

  2. Final optimum solution can be achieved by using an optimum solution of smaller sub-problems.

  3. Dynamic algorithms use memorization.

dynamic programming approach

然而，在一个问题中，两个主要属性可以表明给定问题可以使用动态规划来解决。它们是：

However, in a problem, two main properties can suggest that the given problem can be solved using Dynamic Programming. They are −

Overlapping Sub-Problems

与分而治之的方法类似，动态规划也结合了子问题的解。它主要用于重复需要一个子问题的解的情况。已计算的解会存储在一个表中，这样无需重新计算它们。因此，当存在重叠子问题时就需要这种技术。

Similar to Divide-and-Conquer approach, Dynamic Programming also combines solutions to sub-problems. It is mainly used where the solution of one sub-problem is needed repeatedly. The computed solutions are stored in a table, so that these don’t have to be re-computed. Hence, this technique is needed where overlapping sub-problem exists.

例如，二分查找没有重叠子问题。然而，斐波那契数的递归程序有许多重叠子问题。

For example, Binary Search does not have overlapping sub-problem. Whereas recursive program of Fibonacci numbers have many overlapping sub-problems.

Optimal Sub-Structure

如果给定问题的最优解可以使用其子问题的最优解获得，则给定问题具有最优子结构属性。

A given problem has Optimal Substructure Property, if the optimal solution of the given problem can be obtained using optimal solutions of its sub-problems.

例如，最短路径问题具有以下最优子结构属性：

For example, the Shortest Path problem has the following optimal substructure property −

如果一个节点 x 位于从源节点 u 到目标节点 v 的最短路径中，则从 u 到 v 的最短路径是从 u 到 x 的最短路径和从 x 到 v 的最短路径的组合。

If a node x lies in the shortest path from a source node u to destination node v, then the shortest path from u to v is the combination of the shortest path from u to x, and the shortest path from x to v.

标准的全对最短路径算法，如 Floyd-Warshall 和 Bellman-Ford，是动态规划的典型示例。

The standard All Pair Shortest Path algorithms like Floyd-Warshall and Bellman-Ford are typical examples of Dynamic Programming.

Steps of Dynamic Programming Approach

动态规划算法是使用以下四个步骤设计的：

Dynamic Programming algorithm is designed using the following four steps −

  1. Characterize the structure of an optimal solution.

  2. Recursively define the value of an optimal solution.

  3. Compute the value of an optimal solution, typically in a bottom-up fashion.

  4. Construct an optimal solution from the computed information.

Dynamic Programming vs. Greedy vs. Divide and Conquer

与贪心算法（着重于局部优化）不同，动态算法的目的是对问题进行整体优化。

In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are motivated for an overall optimization of the problem.

与分治算法（将解组合在一起以达到最终解）不同，动态算法使用子问题的结果，然后尝试优化更大的子问题。动态算法利用记忆化来记住已解决子问题的输出。

In contrast to divide and conquer algorithms, where solutions are combined to achieve an overall solution, dynamic algorithms use the output of a smaller sub-problem and then try to optimize a bigger sub-problem. Dynamic algorithms use memorization to remember the output of already solved sub-problems.

Examples of Dynamic Programming

以下计算机问题可以使用动态规划方法解决 −

The following computer problems can be solved using dynamic programming approach −

  1. Matrix Chain Multiplication

  2. Floyd Warshall Algorithm

  3. 0-1 Knapsack Problem

  4. Longest Common Subsequence Algorithm

  5. Travelling Salesman Problem (Dynamic Approach)

动态规划可以按照自顶向下和自底向上的方式使用。当然，大多数时候，参考之前的解输出比在 CPU 周期方面重新计算更便宜。

Dynamic programming can be used in both top-down and bottom-up manner. And of course, most of the times, referring to the previous solution output is cheaper than re-computing in terms of CPU cycles.