动态规划
约 706 字大约 2 分钟
2026-05-11
题型类型
- 最值型 如:最长递增子序列、最小路径和、最大子数组和。 特点:题目通常出现“最长/最短/最多/最小”等字眼。
- 计数型 如:不同路径、爬楼梯方式数、组合总数。 特点:求所有可能方案的总数。
- 存在性/可行性型 如:能否分割等和子集、能否到达终点(跳跃游戏)。 特点:问“是否可能/能否达成”,结果通常是布尔值。
- 序列/字符串匹配型 如:编辑距离、最长公共子序列、通配符匹配。 特点:两个或多个序列之间的对齐或转换操作。
- 区间DP 如:戳气球、最优二叉搜索树、矩阵链乘。 特点:问题定义在某个区间上,大区间依赖内部子区间。
- 状态压缩DP 如:旅行商问题(TSP)、覆盖棋盘问题。 特点:状态用二进制位表示,n一般较小(≤20)。
算法思路
四步法(万能思考模板)
- 定义状态:
dp[i]或dp[i][j]代表什么含义?要尽可能清晰、简洁。 - 找状态转移方程:思考当前状态如何从之前的状态推导过来(分情况讨论)。
- 初始化:边界条件(
dp[0]、dp[1]或空串/空数组时的值)。 - 确定答案:通常返回
dp[n]或max(dp[0..n])等。
- 定义状态:
何时使用DP而不是贪心或回溯
- 贪心:每一步选局部最优,不回头。如果你能证明局部最优就是全局最优,用贪心(如活动安排、找零问题中特定币值)。
- 回溯/DFS:穷举所有可能,没有重叠子问题,或者数据很小(如n≤20)。
- DP:有重叠子问题 + 最优子结构。典型信号:题目中“子序列/子数组/子集”,且暴力递归中存在大量重复计算。
优化技巧
- 空间优化:如果当前状态只依赖前几行/前几列,可以用滚动数组(如斐波那契只需两变量,背包问题中二维变一维)。
- 降低维度:观察状态定义中是否有冗余信息。例如,最长递增子序列的二分优化版从O(n²)到O(n log n)。
- 预处理:先计算一些辅助数组(前缀和、后缀最值),让转移方程更快。
常见易错点
- 循环顺序:确保用到的子状态已经被计算过。比如背包问题中,一维数组要逆序遍历物品重量。
- 无效状态处理:用
-inf或inf表示不可达状态(求最大时用负无穷,求最小时用正无穷)。 - 越界检查:
i-1、j-1处注意初始边界。
版权所有
版权归属:FelixJY
