动态规划

8/9/25About 1 min

线性 DP

状态只与前一两个结果有关，通常是从前往后推导
常用于： 爬楼梯、打家劫舍、最大子序和、最长上升子序列

状态依赖于一个区间的子问题结果，通常双重循环枚举区间
常用于： 戳气球、矩阵链乘、回文分割、石头合并

给定容量与物品，判断是否能放下、放几件或最大价值
常用于： 0-1 背包、完全背包、子集和问题、分割等和子集

基于树的结构，通过后序遍历对子问题求解
常用于： 树的直径、节点权值选择、最大独立集问题

用位运算压缩状态，解决组合数量大的问题
常用于： 旅行商问题（TSP）、排列组合类问题、掷骰子和为目标值

比较两个字符串或数组之间的匹配关系
常用于： 最长公共子序列、编辑距离、正则表达式匹配

状态转移中有“选 or 不选”的决策过程
常用于： 子集、打家劫舍、股票买卖、多段选择问题