动态规划 动态规划是解决多阶段决策优化问题的一种数学方法。它的核心思想是将复杂问题分解为相互关联的子问题，通过求解子问题并记录其解（避免重复计算），最终组合得到原问题的最优解。 核心思想与基本原理 动态规划适用于具有“最优子结构”和“重叠子问题”性质的问题。 最优子结构 ：一个问题的最优解包含其子问题的最优解。也就是说，我们可以通过子问题的最优解来构造原问题的最优解。 重叠子问题 ：在递归地求解问题的过程中，相同的子问题会被反复计算多次。 动态规划通过“记忆化”（存储已解决的子问题的答案）来避免重复计算，从而大幅提高效率。其求解方式通常分为两种： 自顶向下的记忆化搜索 ：从原问题出发，递归地分解问题。在求解每个子问题后，将其结果存储在一个表格（通常称为DP表）中。下次遇到相同子问题时，直接查表获取结果，而无需重新计算。 自底向上的递推法 ：从最小的子问题开始求解，逐步构建更大规模问题的解。这种方法需要先定义子问题的求解顺序，并系统地填充DP表。这是更常用、更经典的方法。 关键概念与步骤 要应用动态规划，需要明确定义以下几个要素： 阶段 ：将问题过程恰当地划分为若干个相互联系的阶段。 状态 ：每个阶段开始时的客观条件。状态必须包含足够的信息，能够描述过程的演变，并且满足“无后效性”——即未来决策只依赖于当前状态，而不依赖于如何到达这个状态的历史路径。 决策 ：当各阶段的状态确定后，可以做出不同的决定，从而演变到下一阶段的某个状态。这个决定称为决策。 状态转移方程 ：确定过程由一个状态到另一个状态的演变规律。它描述了如何从当前阶段的状态和决策，得到下一阶段的状态。状态转移方程是动态规划的核心。 基本步骤 ： 定义子问题/状态 ：确定DP表中每个位置 dp[i] 所代表的含义。 建立状态转移方程 ：找出子问题之间的关系，即如何从 dp[0] , dp[1] , ..., dp[i-1] 等已知结果推导出 dp[i] 。 确定初始条件（边界条件） ：最小的、不可再分的子问题的解是什么。这是递推的起点。 确定计算顺序 ：明确应该以何种顺序（如从前到后、从后到前）填充DP表，以确保在计算 dp[i] 时，它所依赖的子问题都已经被计算过。 构造最优解 ：有时我们只需要最优值，有时还需要知道取得最优值的具体决策序列。这通常需要通过DP表反向追踪来实现。 经典应用示例：最短路径问题 考虑一个网格，从左上角出发，每次只能向右或向下移动一步，到达右下角。每个格子有一个数值（代表通过该格子的成本），求总成本最小的路径。 阶段 ：每一步移动就是一个阶段。 状态 ： dp[i][j] 表示从起点 (0, 0) 到达格子 (i, j) 的最小成本。 状态转移方程 ：要到达 (i, j) ，只能从其上方的 (i-1, j) 或左方的 (i, j-1) 过来。因此，最小成本是来自这两个方向的最小值加上当前格子的成本： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j] 。 初始条件 ：起点成本就是其自身的成本，即 dp[0][0] = cost[0][0] 。此外，网格第一行的格子只能从左边过来，第一列的格子只能从上边过来，这些是边界条件。 计算顺序 ：按行或按列从左到右、从上到下依次填充整个DP表。 构造最优解 ：填充完DP表后， dp[n-1][m-1] 就是最小成本。通过从终点反向追踪（比较 dp[i-1][j] 和 dp[i][j-1] ，选择更小的那个方向），可以还原出整条路径。 与其他方法的比较与进阶话题 与分治法的区别 ：分治法也将问题分解为子问题，但子问题通常是独立的、不重叠的（如归并排序）。动态规划则专门处理子问题相互重叠的情况。 与贪心算法的区别 ：贪心算法每一步都做出当前看来最优的选择，期望达到全局最优，但它不能保证对所有问题都得到全局最优解。动态规划则会考虑所有可能的决策，通过比较来保证全局最优性。 常见模型 ：除了网格路径，动态规划还有多种经典模型，如： 背包问题 ：在容量限制下，选择物品使得总价值最大。 最长公共子序列 ：找出两个序列共有的、最长的子序列。 矩阵链乘法 ：确定矩阵相乘的最优顺序，使得标量乘法次数最少。 挑战 ：动态规划的主要挑战在于正确地定义“状态”和找出“状态转移方程”，这需要对问题有深刻的洞察力。状态定义的不同会直接导致算法效率和复杂度的差异。对于复杂问题，状态空间可能非常大（“维数灾难”），需要更高级的技巧进行优化。