Dynamic programming — 动态规划

动态规划（DP；英语：dynamic programming）是一种将复杂优化问题分解为一系列更简单的子问题来求解的方法。该方法适用于多阶段决策过程，在这些过程中，整个问题的最优解可以由其子问题的最优解构建而成。

该术语由美国数学家理查德·贝尔曼（Richard Bellman）在20世纪50年代引入。在此背景下，「规划」（programming）一词意为「计划」或「制定最优行动方案」，而非编写计算机代码。

关键属性与定理

动态规划能否应用于某个问题，取决于该问题是否具备两个基本属性。

贝尔曼最优性原理

该方法的核心概念是贝尔曼最优性原理（英语：Bellman's principle of optimality）。它指出：无论初始状态和初始决策如何，后续的决策都必须构成一个相对于由初始决策导致的状态的最优策略。

换言之，最优路径的任何一部分本身也是最优的。这一性质使得我们可以将整个问题分解为一系列更简单的子问题，并以递归方式求解。

重叠子问题

如果一个问题在递归求解过程中会多次遇到相同的子问题，那么它就具有重叠子问题（英语：overlapping subproblems）的性质。动态规划通过保存已解决子问题的解（这种技术称为记忆化或制表法）来避免重复计算，从而显著提高了相比于朴素递归搜索的效率。

贝尔曼方程

从最优性原理可以推导出该方法的基本递推关系——贝尔曼方程。它将当前状态的「价值」（最优收益或成本）与后续状态的价值联系起来。对于具有可加目标函数的确定性多阶段过程，其一般形式如下：

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

其中：

• $k$ — 步骤编号（从 $m$ 到 1）；
• $x$ — 系统在步骤 $k-1$ 时的状态；
• $y$ — 在步骤 $k$ 时做出的控制决策；
• ${\phi }_k(x,y)$ — 第k步的收益（或成本）；
• $f_k(x,y)$ — 定义系统新状态的函数；
• $V_k(s)$ — 对于从步骤 $k$、状态 $s$ 开始的子问题，其目标函数的最优值。

该方程通常通过「从后向前」的方式，即从最后一步到第一步，依次求解。

应用示例

• 图中的最短路径问题：该问题具有最优子结构性质，因为最短路径的任何一部分本身也是最短路径。贝尔曼-福特（Bellman-Ford）算法和弗洛伊德-沃歇尔（Floyd-Warshall）算法是应用动态规划解决该问题的经典示例。
• 背包问题：这是一个在容量有限的背包中，选择不同价值和重量的物品以实现最优填充的问题。动态规划通过逐个考虑物品，并在每一步计算所有可能的剩余容量下的最大价值来解决此问题。
• 资源分配问题：将有限的资源（例如投资）分配给多个项目，以实现总体效益的最大化。

局限性

该方法的主要局限性在于维度灾难（英语：curse of dimensionality），这个术语由贝尔曼引入，用以描述随着描述系统状态的变量数量增加，状态数量以及计算复杂性呈指数级增长的现象。这限制了精确动态规划在超高维度问题中的实际应用。