动态规划通过将问题分解为重叠子问题并记录中间结果避免重复计算，分为自顶向下（记忆化搜索）和自底向上（递推填表）两种模式。经典模型包括背包问题（01背包、完全背包）、最长公共子序列（LCS）和区间 DP（矩阵链乘法）。其核心在于设计状态转移方程，例如在编辑距离问题中定义 dp[i][j] 表示字符串 A 前 i 位到 B 前 j 位的操作次数。优化手段包括滚动数组降维、斜率优化（单调队列）和四边形不等式。树形 DP（如求树的最大独立集）和状压 DP（如旅行商问题）进一步扩展了应用场景，需结合问题特性灵活设计状态。
回到总目录
