动态规划从入门到精通：5大核心算法与7个实战案例解析
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
动态规划（Dynamic Programming）是一种通过将复杂问题分解为重叠子问题，并存储子问题解来避免重复计算的算法思想。它的核心在于状态定义、状态转移方程和最优子结构的发现。无论是最短路径问题、背包问题还是字符串编辑距离，动态规划都能通过巧妙的状态设计将指数级复杂度降至多项式级别。本文将带你从基础概念到实战应用，系统掌握动态规划的思维方法与优化技巧。
一、动态规划基础概念：从斐波那契到状态定义
1.1 动态规划与递归的本质区别
💡核心区别：动态规划通过存储中间结果（ memoization ）避免重复计算，而普通递归可能导致指数级时间复杂度。
以斐波那契数列为例：
- 递归解法：
fib(n) = fib(n-1) + fib(n-2)，时间复杂度 O(2ⁿ) - 动态规划解法：用数组存储已计算的 fib 值，时间复杂度 O(n)
def fib_dp(n): dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]1.2 状态定义三要素
📌状态定义三要素：
- 定义维度：问题需要描述的参数（如位置、数量、状态标记）
- 值的含义：该状态下的最优解或计数结果
- 边界条件：最小子问题的解
例如爬楼梯问题：
- 状态定义：
dp[i]表示爬到第 i 级台阶的方法数 - 转移方程：
dp[i] = dp[i-1] + dp[i-2] - 边界条件：
dp[0] = 1（起点），dp[1] = 1
二、状态转移方程设计：从数学归纳到问题建模
2.1 线性DP：最长上升子序列
问题：给定数组nums，求最长严格递增子序列的长度。
状态定义：dp[i]表示以nums[i]结尾的最长上升子序列长度
转移方程：dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]
时间复杂度：O(n²)
def length_of_lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)2.2 区间DP：矩阵链乘法
问题：给定矩阵序列，求最小乘法次数。
状态定义：dp[i][j]表示计算矩阵 i 到 j 的最小代价
转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i]p[k+1]p[j+1])
边界条件：dp[i][i] = 0
核心思想：将大区间分解为小区间，通过小区间的最优解推导大区间的最优解。
三、空间优化策略：从O(n²)到O(n)的突破
3.1 滚动数组优化技巧
当状态转移只依赖前几行数据时，可使用滚动数组将二维空间压缩为一维。
案例：0-1背包问题优化
- 原始DP：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) - 优化后：
dp[j] = max(dp[j], dp[j-w[i]] + v[i])（逆序遍历）
def knapsack_01(weights, values, capacity): dp = [0] * (capacity + 1) for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) return dp[capacity]3.2 状态压缩：位运算与状态编码
对于状态可枚举的问题（如旅行商问题），可用位运算压缩状态表示：
- 状态定义：
dp[mask][u]表示访问过的节点集合为mask，当前在节点u的最小路径 - 空间复杂度：O(n·2ⁿ)，远优于 O(n²·2ⁿ) 的原始表示
四、实战专题：经典问题与变式拓展
4.1 路径规划问题：数字三角形
问题：从三角形顶部走到底部，每次只能向下或右下走，求路径数字和的最大值。
状态定义：dp[i][j]表示到达第 i 行第 j 列的最大和
转移方程：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
def minimum_total(triangle): n = len(triangle) for i in range(1, n): for j in range(i + 1): left = triangle[i-1][j-1] if j > 0 else float('-inf') right = triangle[i-1][j] if j < i else float('-inf') triangle[i][j] += max(left, right) return max(triangle[-1])4.2 状态机DP：股票买卖问题
问题：最多完成 k 笔交易，求最大利润。
状态定义：dp[i][k][0/1]表示第 i 天，第 k 次交易，持有/不持有股票的最大利润
转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i])dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
优化技巧：当 k 大于 n/2 时，等价于无限次交易，可简化为贪心算法。
五、进阶技巧与常见陷阱
5.1 动态规划 vs 贪心算法
| 特性 | 动态规划 | 贪心算法 |
|---|---|---|
| 最优子结构 | 必须满足 | 必须满足 |
| 重叠子问题 | 必须有 | 可以没有 |
| 决策方式 | 自底向上/自顶向下 | 局部最优选择 |
典型案例：
- 贪心适用：活动选择问题（无后效性）
- DP适用：最长公共子序列（有后效性）
5.2 常见陷阱分析
状态定义模糊
❌ 错误：dp[i]表示前 i 个元素的最大和
✅ 正确：dp[i]表示以第 i 个元素结尾的最大子数组和边界条件遗漏
爬楼梯问题中忘记定义dp[0] = 1，导致计算错误空间未优化
二维DP数组在大数据量下可能导致内存溢出
5.3 插头DP：复杂状态建模
插头DP通过记录轮廓线上的"插头"状态，解决网格类问题（如棋盘覆盖、回路计数）。其核心是用状态压缩表示当前行的连通性信息，典型应用于"棋盘染色"和" Hamiltonian 回路"问题。
总结与扩展学习
动态规划的核心思维是用空间换时间和问题分解。掌握动态规划需要：
- 多思考状态定义的合理性
- 熟练推导转移方程
- 灵活运用空间优化技巧
扩展资源：
- 官方文档：docs/dp/
- 专题练习：docs/dp/examples/
通过大量练习，你会发现看似复杂的问题往往可以通过简单的状态定义迎刃而解。动态规划不仅是一种算法，更是一种将复杂问题系统化拆解的思维方式。
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
