动态规划 VS 递推
一句话理解
> 递推:从已知条件出发,顺着公式一步步推出结果。
> 动态规划:把大问题拆成小问题,记录小问题的答案,避免重复计算。
两者很像,但动态规划更“聪明”——它能处理有选择的问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、核心区别
对比项 递推 动态规划 核心思想 用公式直接推出下一项 在多个选择中挑最优的 有没有选择 没有,结果唯一 有,需要比较选最优 状态转移 dp[i] = f(dp[i-1]) dp[i] = min(dp[i-1], dp[i-2]) + cost 经典例子 斐波那契、阶乘 背包问题、最长上升子序列
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、例子对比
例子1:斐波那契数列
递推写法(没有选择,直接算):
例子2:爬楼梯(每次可以爬1阶或2阶)
动态规划写法(有选择,要比较):
> 注意:爬楼梯虽然用加法,但本质是方案数的累加,不是比较选最优。真正的动态规划通常涉及 max/min 的选择。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例子3:最小花费爬楼梯(真正有选择)
题目:每阶楼梯有一个花费 cost[i]。可以从第0阶或第1阶出发,每次爬1阶或2阶,求到顶层的最小总花费。
这里就有“选择”了:要从i-1过来还是从i-2过来?选花费更小的那个。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、什么时候用递推,什么时候用DP?
问题特征 用什么 例子 结果唯一,按公式直接推 递推 斐波那契、阶乘、前缀和 有多种选择,要挑最优 动态规划 背包、最短路径、最小花费 求“有多少种方案” 都可以(通常是DP) 爬楼梯、路径计数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、经典例子对比
递推经典:兔子繁殖(斐波那契)
DP经典:01背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、总结表
递推 动态规划 有没有选择 没有 有(max/min) 状态转移 dp[i] = f(dp[i-1]) dp[i] = max/min(...) 复杂度 O(n) 通常 O(n²) 或更高 典型应用 斐波那契、阶乘 背包、LIS、编辑距离
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
记忆口诀
> 递推公式定好了,顺着往下直接跑
> 动态规划选择多,哪个最优比较过
> 斐波那契是递推,背包问题才DP
> 两者都要记状态,只是DP更复杂