2.1　动态规划法简介

动态规划法的核心思想是将待求解的问题分解为若干个嵌套的子问题，先自底向上地求解子问题，然后从子问题的解回溯得到原问题的解。“动态”即指问题是由一系列变化的状态组成的，状态能随时间的变化而变化，这正符合由马尔可夫决策过程所描述的强化学习的特点。

动态规划和分治法都使用了“分割、求解、合并”的思路。它们的不同点在于分治法分割得到的子问题是相互独立的，子问题的解经过一些简单的合并即可得到原问题的解，而动态规划的子问题是嵌套的，需要自底向上递归地求解子问题。递归求解子问题时会出现子问题重复计算的问题，动态规划法使用一个备忘录来记录所有子问题的解，当待求的子问题已经被录入备忘录时，就可以直接调用结果而无须重复计算，维持备忘录的过程也就是求解问题的过程，备忘录制作完成后原问题的解也就得到了。

用动态规划求解一个问题的步骤如下。

步骤1：找出最优解的性质，并刻画其结构特征。

步骤2：递归地定义子问题和子问题的解。

步骤3：以自底向上的方式求解子问题。

步骤4：根据子问题的解和解的结构回溯构造原问题的最优解。

以下用一个简单的案例来说明如何用动态规划求解一个问题。

【例2-1】　如图2-1所示，从A到F要依次经过一系列中间节点，每两个相邻节点之间都有多条距离不等的路径可以选择。求解从A到F的最短路径。

图2-1　动态规划示意图

例2-1的最优解是显然的，由相邻两点间的最短路径组成的路径就是从A到F的最短路径。以下用动态规划法来得到这一结论。

首先可以断定，从E到F的最短路径一定是从A到F的最短路径的一部分。否则可以用从E到F的最短路径替换当前从A到F的最短路径的E到F段部分，这样就会得到一条比当前A到F的最短路径更短的路径，这和当前路径是从A到F的最短路径是矛盾的，从而得到断定正确。

同理，从A到E的最短路径也应该是从A到F的最短路径的一部分。于是可以得到最短路径的一个性质：

也就是说，要计算总最短路径，只要分别计算从A到E的最短路径和从E到F的最短路径。从E到F的最短路径是容易计算的，而从A到E的最短路径又可以做同样的分析。以此类推，可以得到从A到F的总最短路径是由相邻两节点间的最短路径组合而成的这一结论。

以上分析中，式（2-1）就体现了最优解的性质和递归定义。在计算最优解时是按照

EF→DF→CF→BF→AF

的顺序进行的，这就是自底向上递归计算。