如何理解动态规划？
2021-12-14 22:01:37
动态规划是一种通过拆解问题并重复利用子问题解来高效求解复杂问题的算法策略，其核心思想是“聪明的懒惰”，即避免重复计算，通过存储中间结果提升效率。
核心概念与步骤
动态规划的关键在于三个核心特性：
1. 分解问题（Subproblem Decomposition）：将大问题拆解为多个相互依赖的子问题。例如，爬楼梯问题中，爬到第n阶的方法数可拆解为“爬到第n-1阶的方法数”与“爬到第n-2阶的方法数”之和。
2. 重叠子问题（Overlapping Subproblems）：子问题在计算过程中被多次重复使用。例如，计算爬到第4阶需用到第3阶和第2阶的结果，而第3阶的计算又依赖第2阶和第1阶，导致第2阶被重复计算。动态规划通过存储这些结果避免重复劳动。
3. 最优子结构（Optimal Substructure）：问题的最优解可通过子问题的最优解构建。例如，爬楼梯的最优解（总方法数）由子问题的解直接相加得到；若问题改为“最少步数”，则需比较子问题的最优解（如从n-1阶或n-2阶上来的步数）并取最小值。
实现方式
动态规划有两种典型实现方法：
1. 填表法（递推）：从最小子问题开始，逐步填充表格（数组）存储中间结果。例如，爬楼梯问题中，初始化dp[1]=1、dp[2]=2，然后通过循环计算dp[i]=dp[i-1]+dp[i-2]，直至dp[n]。此方法按顺序解决问题，适合子问题依赖关系明确的情况。
2. 记忆化搜索（递归+缓存）：通过递归分解问题，但用缓存（如字典或数组）存储已计算的子问题结果。例如，递归函数climb_stairs_recursive(n)会先检查memo[n]是否存在，若存在则直接返回，否则递归计算n-1和n-2的结果并存储。此方法更接近人类思维，但需注意递归深度限制。
适用场景与经典问题
当问题满足以下两点时，可考虑动态规划：
- 最优子结构：问题的解依赖子问题的解。
- 重叠子问题：子问题被多次重复计算。
经典问题包括： - 背包问题：在容量限制下最大化物品总价值。
- 最长公共子序列（LCS）：找出两个字符串的最长公共子串。
- 编辑距离：计算字符串转换所需的最少操作次数。
- 硬币找零问题：用最少硬币凑成目标金额。
总结“套路”
- 定义状态：明确dp[i]或dp[i][j]的含义（如dp[i]表示爬到第i阶的方法数）。
- 状态转移方程：建立子问题与当前问题的数学关系（如dp[i]=dp[i-1]+dp[i-2]）。
- 初始条件：确定最小子问题的解（如dp[1]=1）。
- 选择实现方式：根据问题特点选择填表法或记忆化搜索。
动态规划的本质是通过“分解”与“重复利用”将复杂问题转化为可管理的子问题集合，掌握其核心思想后，许多看似复杂的问题均可迎刃而解。
热门标签
