动态规划的基本原理与应用 描述 动态规划（Dynamic Programming，DP）是一种解决复杂问题的算法思想，常用于优化问题（如求最大值、最小值或计数）。其核心思想是将原问题分解为相互重叠的子问题，通过解决子问题并存储结果（避免重复计算），最终合并得到原问题的解。与分治法不同，动态规划的子问题通常不是独立的。 解题过程循序渐进讲解 识别动态规划问题的特征 重叠子问题 ：问题可分解为多个重复出现的子问题（例如斐波那契数列中，计算 F(n) 需重复计算 F(n-1) 和 F(n-2) ）。 最优子结构 ：问题的最优解包含子问题的最优解（例如最短路径问题中，A到C的最短路径包含A到B的最短路径）。 无后效性 ：当前状态一旦确定，后续决策不受之前状态的影响（例如棋盘路径问题中，移动方向只依赖当前位置）。 定义状态与状态转移方程 状态表示 ：用变量（如 dp[i] 或 dp[i][j] ）表示子问题的解。例如在斐波那契数列中， dp[i] 表示第 i 个斐波那契数。 状态转移方程 ：描述状态之间的关系。例如斐波那契数列的方程为： \[ dp[ i] = dp[ i-1] + dp[ i-2 ] \quad (i \geq 2) \] 初始化边界条件 ：确定最小子问题的解。例如 dp[0] = 0, dp[1] = 1 。 选择计算顺序：自底向上或自顶向下 自底向上（迭代） ：从最小子问题开始逐步计算到原问题。例如计算斐波那契数列时，从 i=2 循环到 i=n 。 自顶向下（记忆化搜索） ：从原问题开始递归分解，但用数组存储已计算的子问题结果，避免重复计算。 优化空间复杂度（可选） 如果状态转移仅依赖有限的前几个状态（如 dp[i] 只依赖 dp[i-1] 和 dp[i-2] ），可用少数变量替代整个数组，将空间复杂度从O(n)降为O(1)。 实例：爬楼梯问题 问题：每次可以爬1或2阶台阶，爬到n阶有多少种方法？ 定义状态 ： dp[i] 表示爬到第i阶的方法数。 状态转移方程 ：爬到第i阶可从第i-1阶爬1阶，或从第i-2阶爬2阶，故： \[ dp[ i] = dp[ i-1] + dp[ i-2 ] \] 初始化 ： dp[0] = 1 （起点）， dp[1] = 1 。 计算顺序 ：自底向上，从 i=2 到 i=n 迭代计算。 优化 ：仅需两个变量保存前两个状态，空间复杂度O(1)。 关键要点 动态规划适用于有重叠子问题的优化问题。 核心步骤是定义状态、建立方程、确定计算顺序。 实际应用中需通过练习识别问题模式（如背包问题、最长公共子序列等）。