1 基本概念
1.1 定义
动态规划是一种求解最优化、计数和决策类问题的方法。其基本做法是将原问题拆分为若干子问题，先求出子问题的结果，再利用这些结果构造原问题的答案。由于许多子问题会被重复访问，动态规划通过记录已计算结果来减少重复运算，从而提高效率。
1.2 核心思想
动态规划的核心在于“分解”和“复用”。它并不追求一次性直接得到全局答案，而是将复杂问题逐层拆开，让每一层的结果都可用于下一层计算。只要问题满足相应性质，这种方法通常能显著降低求解成本。
1.2.1 最优子结构
最优子结构指一个问题的最优解可以由若干子问题的最优解组合得到。换言之，如果整体方案是最优的，那么其组成部分在各自子问题中也应当是最优的。这一性质使得从小规模解推导大规模解成为可能。
1.2.2 重叠子问题
重叠子问题是指在求解过程中，同一子问题会被多次计算。若不加记录，递归展开时容易造成大量重复工作。动态规划正是利用缓存或表格保存中间结果，使每个子问题通常只需计算一次。
1.3 适用条件
并非所有问题都适合动态规划。一般来说，若问题能拆分为规模更小且彼此关联的子问题，并且中间结果可被重复利用，那么就具备使用动态规划的基础条件。
1.3.1 状态可分解性
状态可分解性要求原问题能够用有限个参数描述，并且这些参数在子问题之间具有自然的继承关系。只有当问题状态能够被清晰拆分时，动态规划才能建立有效的转移过程。
1.3.2 结果可复用性
结果可复用性意味着子问题的答案具有稳定性，且后续计算可以直接引用这些答案，而无需重新求解。若子问题结果难以复用，动态规划的优势就会明显下降。
2 历史与发展
2.1 早期思想来源
动态规划的思想可以追溯到对多阶段决策问题的研究。早期数学家和工程技术人员在处理资源分配、路线选择等问题时，已经开始采用“逐步决策、逐步优化”的思路，只是尚未形成统一名称。
2.2 理论体系形成
随着最优化理论和控制理论的发展，动态规划逐渐形成较完整的数学框架。其关键思想在于把复杂过程表示为一系列阶段，并利用阶段间的递推关系建立统一求解方式，这使其从经验方法上升为系统理论。
2.3 在计算机科学中的普及
计算机的出现使动态规划从理论工具转变为广泛可用的算法范式。尤其在程序设计中，借助数组、递归和缓存机制，动态规划能够被高效实现，因此在算法竞赛、软件工程与科研计算中迅速普及。
3 数学基础
3.1 状态与状态空间
状态是对问题当前阶段情况的抽象描述，通常由若干变量组成。所有可能状态构成状态空间。合理的状态设计是动态规划成功的前提，因为状态既要足够表达问题，又要尽量简洁，以控制复杂度。
3.2 状态转移
状态转移描述的是从一个状态推导到另一个状态的关系。它通常通过选择、合并、扩展或比较等操作实现。状态转移方程把局部关系写成可计算的公式，是动态规划的核心表达形式。
3.3 最优性原理
最优性原理说明，整体最优解的任一前缀或子结构，也必须是相应子问题的最优解。该原理为动态规划提供了理论依据，使得局部最优信息能够可靠地构造全局答案。
3.3.1 Bellman 最优性原理
Bellman 最优性原理强调：无论初始决策如何，一个最优策略在任何中间状态之后所做出的后续决策，也应构成该中间状态下的最优策略。该原理是现代动态规划的重要基础之一。
3.3.2 递推关系
递推关系将一个状态的值表示为若干更小状态值的函数。通过从边界状态逐步向上计算，便可得到目标状态的结果。递推关系形式多样，但都体现了“由已知推未知”的思想。
3.4 边界条件与初始条件
边界条件定义最小规模或特殊状态下的答案，初始条件则为递推提供起点。若边界设置错误，即便转移方程正确，最终结果也可能偏离预期，因此这一步在建模中非常关键。
4 设计方法
4.1 问题建模
动态规划设计通常从问题建模开始，需要先识别阶段、选择、约束与目标。只有把实际问题转化为结构清晰的状态系统，后续的转移和计算才具有可操作性。
4.2 状态定义
状态定义决定了动态规划的规模与表达能力。常见做法是用“前 i 个元素”“当前位置”“剩余资源”“当前区间”等方式描述问题进度。状态过细会导致复杂度上升，过粗则可能丢失必要信息。
4.3 转移方程构造
转移方程用于描述一个状态如何由前驱状态得到。构造时通常需要分析最后一步、最后一次选择或最后一个区间划分点。良好的转移方程应当完整覆盖所有合法情况，并避免重复计入。
4.4 目标函数与评价标准
在优化类问题中，需要明确目标函数，即要求最大化、最小化还是统计某种数量。评价标准则决定了不同方案之间如何比较。目标明确后，动态规划才能围绕统一准则进行更新。
4.5 结果恢复
有些动态规划不仅要求输出最优值，还需要还原具体方案。结果恢复通常通过记录决策路径、前驱状态或选择标记实现。该过程使动态规划结果更具可解释性与可操作性。
5 实现方式
5.1 自顶向下方法
自顶向下方法从最终目标出发，通过递归不断分解问题，直到到达边界状态。其优点是思路直观，常与记忆化技术结合使用。
5.1.1 记忆化搜索
记忆化搜索是在递归过程中保存已经求出的状态值。当同一状态再次出现时，直接返回缓存结果，从而避免重复展开。它在结构清晰、状态分支较多的问题中尤为常见。
5.1.2 递归实现
递归实现更接近问题定义本身，写法简洁，便于表达复杂依赖关系。不过，若递归层数过深，可能带来栈空间压力，因此在大规模数据下需注意实现细节。
5.2 自底向上方法
自底向上方法从基础状态开始，按照一定顺序逐步填充表格，最终得到目标状态答案。这种方式通常便于控制计算顺序，也更适合进行空间优化。
5.2.1 表格法
表格法使用数组或矩阵存储各状态的值。只要转移顺序安排合理，就可以逐项更新并最终获得结果。它是动态规划最经典的实现形式之一。
5.2.2 滚动数组优化
滚动数组利用状态只依赖少量前序层的特点，减少表格存储。通过保留必要的前一层或若干层数据，可显著压缩空间，但要求转移顺序非常谨慎。
5.3 空间优化
空间优化的目标是在不改变结果的前提下减少存储需求。对于状态规模较大的问题，这往往直接决定算法能否实际运行。
5.3.1 状态压缩
状态压缩通过位运算或编码方式，把多个维度的信息合并到较少变量中。它常用于集合型、排列型和棋盘型问题，能够在有限空间内表示更多状态。
5.3.2 剪枝与降维
剪枝是提前排除无效或劣势状态，降维则是通过重新组织状态变量减少维数。二者都能减轻计算负担，但前提是不能破坏原有转移的正确性。
6 典型问题
6.1 背包问题
背包问题是一类经典动态规划模型，核心是在容量限制下选择物品，使总价值或总收益最优。它能很好体现状态定义、转移和边界处理的基本思路。
6.1.1 0-1 背包
0-1 背包中，每件物品只能选一次或不选。其状态通常表示“前若干件物品、当前容量”下的最优值，是入门动态规划的重要范例。
6.1.2 完全背包
完全背包允许每件物品被重复选择。与0-1背包相比，转移方向和循环顺序会有所不同，因此常被用来训练对状态依赖的理解。
6.1.3 多重背包
多重背包介于前两者之间，每件物品有固定数量上限。常见处理方式包括逐件拆分、二进制优化或单调队列优化，以提高效率。
6.2 序列类问题
序列类问题通常研究字符串、数组或时间序列上的匹配、比较与变化规律，动态规划在其中尤为常见。
6.2.1 最长公共子序列
最长公共子序列用于寻找两个序列中保持相对顺序的公共部分，常见于文本比较与生物序列分析。其状态转移清晰，是序列动态规划的代表。
6.2.2 最长递增子序列
最长递增子序列研究序列中按原顺序选出的严格递增部分。它既可以用经典动态规划求解，也可通过更高效的辅助结构进行优化。
6.2.3 编辑距离
编辑距离衡量两个字符串之间通过插入、删除和替换变换所需的最少操作数。该问题常用于拼写纠错、自然语言处理与文本相似度计算。
6.3 区间类问题
区间类问题关注连续片段上的合并、拆分与最优组合，适合用区间端点作为状态描述。
6.3.1 区间合并
区间合并类问题通常要求将若干片段按规则合并成整体，并使代价最小或收益最大。其转移往往围绕区间划分点展开。
6.3.2 区间划分
区间划分关注如何把一个整体划分为若干连续部分，使目标值最优。此类问题常出现在括号匹配、石子合并等模型中。
6.4 图与路径问题
图与路径问题中，动态规划常用于求解特定结构上的最短、最长或可行路径。
6.4.1 最短路径变体
在某些带阶段限制、层次限制或额外约束的图问题中，传统最短路算法不易直接应用，动态规划可通过状态扩展来处理这些变体。
6.4.2 网络流中的动态规划思想
网络流问题本身不完全等同于动态规划，但在分阶段增广、路径选择和容量约束分析中，常能看到动态规划式的递推思维。
6.5 计数类问题
计数类问题要求统计满足条件的方案数、路径数或组合数，动态规划可以系统地累加合法状态。
6.5.1 方案数统计
方案数统计关注有多少种方式达到某种目标。与优化问题相比，它更强调“可行性累积”，只要状态定义合理，常能获得简洁递推。
6.5.2 概率与期望递推
在随机过程和随机决策中，动态规划也可用于计算概率和期望。此时状态值不再是整数，而可能是概率、期望或其他实数指标。
7 常见变体
7.1 线性动态规划
线性动态规划通常指状态按一维顺序推进的问题，如前缀、后缀或位置型转移。它形式简洁，常作为入门模型。
7.2 区间动态规划
区间动态规划以区间长度递增为顺序，适用于依赖区间整体结构的问题。由于转移常涉及枚举分割点，因此在实现上较为典型。
7.3 树形动态规划
树形动态规划处理以树为结构的问题，状态通常在父子节点之间传递。它广泛用于层次结构优化、树上选取与覆盖类任务。
7.4 状态压缩动态规划
状态压缩动态规划常用于小规模但维度较高的状态集合，如棋盘、子集和排列问题。通过位表示法，可以把多个离散信息压入单个整数中。
7.5 数位动态规划
数位动态规划针对数字范围上的统计问题，按照数位逐位递推。它适合处理“在某个上界以内满足条件的数有多少”之类的任务。
7.6 概率动态规划
概率动态规划把状态值定义为概率分布、期望值或随机事件的累计结果。它常用于博弈分析、随机过程和不确定环境下的决策问题。
8 复杂度分析
8.1 时间复杂度
动态规划的时间复杂度主要由状态数和每个状态的转移次数决定。若状态设计合理且转移有限，其复杂度通常远低于暴力搜索，但在高维问题中仍可能较高。
8.2 空间复杂度
空间复杂度取决于需要保存多少状态值。若采用自底向上表格，空间可能较大；而通过滚动数组、压缩存储等手段，常可将存储需求明显降低。
8.3 状态数与转移数
状态数决定“要算多少个点”，转移数决定“每个点要看多少前驱”。这两个量共同构成动态规划性能的核心指标，也直接影响算法可行性。
8.4 优化前后对比
在未优化时，动态规划往往以完整表格保存全部状态，方便理解但占用较多资源。经过空间压缩、剪枝或单调结构优化后，通常可以在保持正确性的同时提升实际效率。
9 正确性证明
9.1 归纳证明
动态规划的正确性常用数学归纳法证明。先验证基础状态成立，再假设较小规模状态正确，进而证明更大状态的转移也正确，最终覆盖整个问题。
9.2 最优性证明
最优性证明关注由子问题最优解组合出的结果是否仍为全局最优。只要状态定义和转移关系与最优子结构一致，便可建立严密的证明链条。
9.3 状态转移合法性
状态转移合法性要求每一步转移都必须符合题目约束，不能遗漏可行方案，也不能引入非法方案。转移合法是动态规划正确性的直接前提。
9.4 边界可行性验证
边界可行性验证用于检查初始状态是否真实反映问题起点。若边界条件错误，后续递推即使形式正确，也可能得到不合理结果。
10 应用领域
10.1 运筹优化
在运筹优化中，动态规划用于处理路径选择、库存控制、组合安排等问题。它能够将复杂的决策过程拆成多阶段分析，适合描述资源受限环境。
10.2 资源调度
资源调度问题常涉及时间、人员、设备或预算的分配。动态规划可以在约束条件下寻找较优安排方案，兼顾效率与可行性。
10.3 金融建模
金融建模中，动态规划可用于分期投资、资产配置和风险决策等问题。通过阶段化处理，它能够描述在不同市场条件下的策略选择。
10.4 机器学习
在机器学习相关任务中，动态规划常用于序列标注、解码、路径搜索和结构化预测。它帮助模型在大量候选方案中找到一致且可计算的最优结构。
10.5 生物信息学
生物信息学中的序列比对、基因片段分析和结构预测，常依赖动态规划框架。由于生物序列往往具有重叠结构，动态规划特别适合此类计算。
10.6 工程与控制
在工程与控制领域，动态规划常被用于最优控制、过程调度和设备运行策略设计。其阶段决策特性与工程系统的时间演化规律较为契合。
11 局限性
11.1 维度灾难
当状态维度过多时，状态数量会呈指数级增长，导致算法难以在有限时间和空间内完成。这种现象常被称为维度灾难。
11.2 状态爆炸
即使问题本身规模不大，若状态定义过细或转移分支过多，也可能出现状态爆炸。此时动态规划的表格会迅速膨胀，降低实用性。
11.3 建模难度
动态规划的难点往往不在计算，而在建模。如何准确抽象状态、确定转移和边界，常比编写代码更具挑战性。
11.4 与贪心、分治的区别
动态规划强调子问题重叠与结果复用；贪心强调局部选择的即时最优；分治则更侧重子问题相互独立。三者都能处理复杂问题，但适用条件不同。
12 经典例题与学习路径
12.1 入门题型
入门阶段通常从斐波那契数列、爬楼梯、简单背包和基本序列问题开始。这些题目结构清楚，有助于理解状态定义和递推写法。
12.2 提高题型
提高题型往往涉及多维状态、路径限制、区间处理或方案统计。此阶段需要训练对题意的抽象能力，以及对边界和转移细节的把握。
12.3 竞赛常见模型
竞赛中常见的动态规划模型包括背包、区间、树形、数位和状态压缩等。熟悉这些模板有助于快速识别题型，并在有限时间内完成建模。
12.4 学习误区与技巧
学习动态规划时，常见误区包括盲目背模板、忽视状态含义、遗漏边界条件以及循环顺序错误。较有效的学习方法是先理解问题结构，再总结常见模型，并通过适量练习巩固。