动态规划基础讲解动态规划Dynamic Programming简称 DP是一种通过把大问题拆成小问题并保存小问题答案来避免重复计算的算法思想。它常用于求最值、计数、可行性判断等问题。一、什么时候可以用动态规划一个问题通常需要满足最优子结构大问题的最优解可以由小问题的最优解推出来。例如爬到第n阶的方法数可以由第n-1阶和第n-2阶推出。重叠子问题不同的大问题会反复用到相同的小问题。例如斐波那契数列中f(5)会反复用到f(3)、f(2)。无后效性当前状态确定后后面的决策只依赖当前状态不依赖“怎么走到这里”的历史路径。二、动态规划解题五步法1. 定义状态明确dp[i]或dp[i][j]表示什么。例如爬楼梯dp[i]表示爬到第i阶的方法数。状态定义是动态规划最核心的一步。2. 推导状态转移方程找dp[i]和之前状态的关系。例如爬楼梯每次可以走 1 阶或 2 阶dp[i] dp[i-1] dp[i-2]3. 初始化确定最小状态的初始值。例如dp[0] 1dp[1] 14. 确定遍历顺序保证计算dp[i]时它依赖的状态已经算出来。例如爬楼梯从小到大遍历foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]5. 返回答案根据题意返回dp[n]、dp[n][m]或所有状态中的最值等。三、经典例子爬楼梯题目每次可以爬 1 阶或 2 阶问爬到第n阶有多少种方法。状态定义dp[i]爬到第i阶的方法数。转移方程最后一步可能从i-1阶走 1 阶上来也可能从i-2阶走 2 阶上来dp[i] dp[i-1] dp[i-2]初始化dp[0] 1 dp[1] 1代码defclimbStairs(n):ifn1:return1dp[0]*(n1)dp[0]1dp[1]1foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]returndp[n]空间优化因为dp[i]只依赖前两个状态所以可以只用两个变量defclimbStairs(n):ifn1:return1a,b1,1foriinrange(2,n1):a,bb,abreturnb四、经典例子0-1 背包题目有n个物品第i个物品重量为w[i]价值为v[i]背包容量为C。每个物品最多选一次求最大价值。状态定义dp[j]容量为j时能获得的最大价值。转移方程对于每个物品dp[j] max(dp[j], dp[j - w[i]] v[i])含义不选当前物品价值是dp[j]选当前物品价值是dp[j - w[i]] v[i]关键点倒序遍历容量0-1 背包中每个物品只能用一次所以容量要倒序遍历defknapsack(C,weights,values):dp[0]*(C1)foriinrange(len(weights)):forjinrange(C,weights[i]-1,-1):dp[j]max(dp[j],dp[j-weights[i]]values[i])returndp[C]如果正序遍历就变成完全背包表示每个物品可以选无限次。五、动态规划和递归、贪心的区别方法特点递归直接拆问题但可能大量重复计算记忆化搜索递归 缓存是动态规划的一种写法动态规划保存子问题结果通常用表格或数组递推贪心每步选局部最优不保证全局最优DP 会综合考虑多个状态很多题可以写成自顶向下记忆化搜索自底向上递推 DP两者本质相同。六、常见动态规划类型线性 DP爬楼梯、打家劫舍、最长递增子序列背包 DP0-1 背包、完全背包、多重背包区间 DP石子合并、最长回文子序列树形 DP树上的最大独立集、树形背包状态压缩 DP用二进制表示状态如旅行商问题数位 DP统计满足数位条件的数字个数七、动态规划常见误区状态定义不清楚先想清楚dp[i]到底表示什么。转移方程漏情况要枚举“最后一步”或“当前决策”的所有可能。初始化错误初始值往往决定结果尤其是计数题和背包题。遍历顺序错误要保证依赖状态先被计算。背包问题中正序和倒序含义不同。空间优化后逻辑混乱一维滚动数组优化前最好先写二维版本验证。八、动态规划做题模板1. 明确 dp 数组含义 2. 写出状态转移方程 3. 初始化 dp 4. 确定遍历顺序 5. 返回目标答案 6. 考虑是否能压缩空间简单记定义状态 → 找转移 → 初始化 → 按序计算 → 返回答案动态规划的核心不是背代码而是练习“如何定义状态”和“如何从子状态推出当前状态”。建议从爬楼梯、打家劫舍、0-1 背包、最长递增子序列这几类题开始练习。学习动态规划前建议补充的知识动态规划本身并不要求你先学很多高深内容但下面这些前置知识会显著降低学习难度。可以分成三类必须会、强烈建议会、按题型补充。一、必须会的基础1. 编程语言基础至少熟练掌握一种语言中的变量、条件判断、循环函数定义与调用数组 / 列表 / 二维数组字符串基本操作索引和边界处理例如 Python 中要熟练写dp[0]*(n1)dp[[0]*(m1)for_inrange(n1)]因为动态规划大量使用数组保存状态。2. 数组与二维表要理解一维数组dp[i]表示某个状态二维数组dp[i][j]表示两个维度下的状态如何初始化数组如何遍历数组如何避免下标越界很多 DP 题本质就是“填一张表”。例如 0-1 背包的一维数组dp[0]*(C1)区间 DP 的二维数组dp[[0]*nfor_inrange(n)]3. 循环与遍历顺序动态规划非常依赖遍历顺序。你需要理解正序遍历和倒序遍历的区别外层循环和内层循环分别代表什么为什么计算dp[i]时它依赖的状态必须已经算好例如 0-1 背包容量必须倒序forjinrange(C,w-1,-1):dp[j]max(dp[j],dp[j-w]v)如果这个不熟后面很容易把 0-1 背包和完全背包写混。4. 递归与函数调用动态规划经常从递归演化而来所以要会递归函数怎么写递归终止条件递归树大概长什么样什么是重复子问题例如斐波那契递归deffib(n):ifn1:returnnreturnfib(n-1)fib(n-2)要能看出它为什么慢fib(3)被重复计算很多次。5. 递推思想递推是动态规划最直接的前置知识。要理解已知前面的结果如何推出后面的结果。例如f(0) 0 f(1) 1 f(i) f(i-1) f(i-2)这其实就是最简单的动态规划。建议先练斐波那契数列爬楼梯杨辉三角简单数列求和二、强烈建议补充的知识1. 复杂度分析至少会估算时间复杂度O(n)、O(n^2)、O(nm)空间复杂度为什么二维 DP 可以优化成一维例如foriinrange(n):forjinrange(m):...这是O(nm)。动态规划题通常要判断状态数 × 每个状态的转移代价。2. 记忆化搜索记忆化搜索是“递归 缓存”是理解 DP 的绝佳桥梁。例如memo{}defdfs(n):ifn1:returnnifninmemo:returnmemo[n]memo[n]dfs(n-1)dfs(n-2)returnmemo[n]学会它之后你会更容易理解什么是状态什么是重复子问题为什么 DP 能优化递归3. 暴力枚举与搜索动态规划很多时候是在优化暴力搜索。建议了解枚举所有选择子集、排列、组合的基本概念DFS 搜索的基本写法搜索树的概念例如 0-1 背包的暴力思路每个物品选或不选枚举所有组合再取最大价值。理解暴力后才能理解 DP 在优化什么。4. 数学归纳思想动态规划的状态转移和数学归纳很像验证初始状态成立假设前面的状态成立推出当前状态成立例如如果知道爬到第i-1阶和第i-2阶的方法数就能推出第i阶。不需要形式化证明但要有这种“由小推大”的思维。5. 边界与初始化很多 DP 错误不是转移方程错而是初始化错。要习惯思考dp[0]应该是什么空集、0 容量、0 个物品怎么处理不可能状态用什么值表示计数题初始值是 0 还是 1求最小值时初始值用多大例如dp[0]*(n1)dp[0]1计数题里dp[0] 1通常表示“空方案也是一种方案”。三、按题型补充的知识不是一开始都要学学到对应 DP 类型前再补即可。1. 学背包 DP 前补充二维数组正序 / 倒序遍历最大最小值更新容量、重量、价值这类建模2. 学线性 DP 前补充一维数组递推前缀思想序列下标处理3. 学区间 DP 前补充二维数组区间[l, r]按区间长度遍历子区间划分4. 学树形 DP 前补充树的基本概念邻接表DFS 遍历树后序遍历思想5. 学状态压缩 DP 前补充二进制位运算、|、^、、用二进制表示集合6. 学数位 DP 前补充数字按位拆分前缀统计思想递归枚举数位四、建议的学习顺序比较平滑的路线是编程基础 → 数组与循环 → 递归 → 递推 → 记忆化搜索 → 复杂度分析 → 简单线性 DP → 0-1 背包 → 完全背包 → 区间 DP / 树形 DP / 状压 DP具体练习可以按这个顺序斐波那契数列爬楼梯杨辉三角打家劫舍最长递增子序列0-1 背包完全背包五、最小前置清单如果只想尽快开始学动态规划至少先掌握数组 / 列表二维数组for 循环与倒序遍历函数和递归递归终止条件斐波那契式递推基本复杂度O(n)、O(n^2)边界和初始化意识一句话总结学 DP 前最该补的是数组、循环、递归、递推、记忆化和复杂度分析。其他如树、位运算、区间思想可以等到对应题型再补。