动态规划
约 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