动态规划是数学优化和计算机科学中的一种方法，通过求解相互关联、结果可复用的子问题来解决问题。动态规划算法不反复计算相同的可能情况，而是明确定义子问题，并按照递推关系组合它们的解。这种方法可用于优化、计数、概率推断以及序贯决策。当许多看似不同的求解路径都通向同一个子问题时，动态规划尤为有效。(ocw.mit.edu)
起源与数学基础
理查德·贝尔曼于20世纪50年代在兰德公司提出并发展了动态规划。他于1957年出版的《动态规划》一书，为多阶段决策过程建立了数学框架。这里的“规划”指制定计划或选择决策，而非专指编写软件。该框架利用优化问题的内部结构，拓展了可求解问题的范围。(rand.org)
其核心思想之一是贝尔曼最优性原理：作出初始决策后，余下的决策必须对该决策所产生的局面而言是最优的。从算法角度看，这与最优子结构密切相关，即一个最优解可以由恰当定义的子问题的最优解组合而成。重叠子问题则提供了节省计算的机会：同一个较小的问题会反复出现，因此可以存储其解并加以复用。(studylib.net)
这些性质取决于如何表述问题。状态必须保留与后续选择有关的全部信息。例如，资源分配问题的状态可能需要同时包含剩余资源和仍可作出的决策；若只记录其中一项，就可能得到无效的递推关系。(ocw.mit.edu)
状态、递推关系与计算
设计动态规划算法需要定义状态、表达状态之间的关系、指定边界情况，并确定计算顺序。一个状态可以描述序列的某个前缀、剩余容量、图中的顶点，或这些量的组合。递推关系规定一个状态的解如何依赖于其他状态的解。在许多有限问题中，这些依赖关系构成一个有向无环图，因此可以在所依赖的状态计算完成后，再计算当前状态的解。(live.ocw.mit.edu)
两种常见的实现方式是：
- **自顶向下的记忆化：**按需计算递归形式的解，存储每个已计算的结果，并在后续再次需要时直接读取。
- **自底向上的制表法：**按照预先确定且符合依赖关系的顺序计算结果，通常通过填充数组或表格实现。
两者都复用子问题的解。记忆化可以避免计算从待求问题出发无法到达的状态，而制表法则明确规定了计算顺序。无论采用哪种方法，都仍需正确定义状态和基本情况。(ocw.mit.edu)
用于优化的表格往往只存储最优值。若要还原实际的决策，还可以记录每个最优值由哪一次转移得到，再沿这些选择反向追溯。当后续计算仅依赖表格中的一小部分时，可以丢弃较早的条目，以减少内存占用。(ocw.mit.edu)
示例：0–1背包问题
在0–1背包问题中，每件物品都有正整数重量 (w_i) 和价值 (v_i)。任务是在总重量不超过容量 (W) 的前提下，选择总价值最大的物品集合，每件物品至多选取一次。定义 (D(i,c)) 为容量为 (c) 时，使用前 (i) 件物品所能取得的最大价值。(live.ocw.mit.edu)
令 (D(0,c)=0)，则递推关系为
[ D(i,c)= \begin{cases} D(i-1,c), & w_i>c,\ \max{D(i-1,c),,v_i+D(i-1,c-w_i)}, & w_i\le c. \end{cases} ]
两种选择分别是不选或选取物品 (i)。两者都只引用前 (i-1) 件物品的结果，从而避免重复选取该物品。所求最优值为 (D(n,W))。这个例子说明了为何状态必须包含剩余容量：不同容量允许后续作出的选择不同。(ocw.mit.edu)
该表有 (O(nW)) 个条目，在通常的算术运算假设下，每个条目所需的计算量为常数。因此，其运行时间是伪多项式时间，相对于输入的二进制长度而言未必是多项式时间：表示 (W) 只需要 (O(\log W)) 位。因此，动态规划并不意味着它所解决的每个问题都有高效的多项式时间算法。(ocw.mit.edu)
序贯决策与随机决策
在序贯优化中，价值函数表示从某个状态出发，未来所能实现的最佳结果。对于确定性的有限时域成本问题，可以采用如下形式的贝尔曼方程：
[ V_t(s)=\min_{a\in A_t(s)} \left[c_t(s,a)+V_{t+1}(f_t(s,a))\right], ]
其中，(a) 是可采取的动作，(c_t) 是其即时成本，(f_t) 是该动作产生的状态。终端条件使递推关系完整。在存在不确定性时，未来成本被替换为对各种可能转移取的期望值。(studylib.net)
对于马尔可夫决策过程，马尔可夫性质确保当前状态充分表示了未来转移所需的信息。价值迭代反复应用最优性更新，而策略迭代则交替进行策略（强化学习）的评估与动作选择的改进。经典动态规划假定转移与奖励模型已知；许多强化学习方法则从经验中估计相关量。存在循环或具有无限时域的模型可能需要反复更新，而不能仅通过一次填表完成计算。(incompleteideas.net)
应用与局限
动态规划是求解最短路径、序列比较和最优括号化等问题的算法基础。编辑距离通过插入、删除和替换等选择，比较字符串的前缀或后缀；矩阵链乘法则选择一种括号化方式，在不改变乘积的前提下，使算术运算量最小。(live.ocw.mit.edu)
在隐马尔可夫模型中，维特比算法寻找概率最大的隐状态序列，而前向算法通过对所有隐状态路径求和来计算观测序列的似然。这些应用表明，动态规划不一定用于优化某个目标：可复用的递推关系也可以用来汇总概率。(web.stanford.edu)
其主要局限在于状态和转移的数量。多维状态空间可能迅速膨胀，造成维数灾难。复用结果能够消除重复计算，但仅凭这一点，无法使规模过大的状态表示变得可处理。(incompleteideas.net)