动态规划 vs 递推

张kk

2026-06-14 09:33:58

发布于：广东

25阅读

0回复

0点赞

动态规划 vs 递推

一句话理解

递推：从已知条件出发，顺着公式一步步推出结果。
动态规划：把大问题拆成小问题，记录小问题的答案，避免重复计算。

两者很像，但动态规划更“聪明”——它能处理有选择的问题。

一、核心区别

对比项	递推	动态规划
核心思想	用公式直接推出下一项	在多个选择中挑最优的
有没有选择	没有，结果唯一	有，需要比较选最优
状态转移	`dp[i] = f(dp[i-1])`	`dp[i] = min(dp[i-1], dp[i-2]) + cost`
经典例子	斐波那契、阶乘	背包问题、最长上升子序列

二、例子对比

例子1：斐波那契数列

递推写法（没有选择，直接算）：

int a[100];
a[1] = 1;
a[2] = 1;
for (int i = 3; i <= n; i++) {
    a[i] = a[i-1] + a[i-2];  // 只有一种算法，没得选
}

例子2：爬楼梯（每次可以爬1阶或2阶）

动态规划写法（有选择，要比较）：

int dp[100];
dp[1] = 1;  // 到第1阶：1种方法
dp[2] = 2;  // 到第2阶：1+1 或 2，共2种

for (int i = 3; i <= n; i++) {
    // 到第i阶 = 从i-1过来 + 从i-2过来
    dp[i] = dp[i-1] + dp[i-2];  // 这里也是加法，但不是“选择”
}

注意：爬楼梯虽然用加法，但本质是方案数的累加，不是比较选最优。真正的动态规划通常涉及 max/min 的选择。

例子3：最小花费爬楼梯（真正有选择）

题目：每阶楼梯有一个花费 cost[i]。可以从第0阶或第1阶出发，每次爬1阶或2阶，求到顶层的最小总花费。

int dp[100];
dp[0] = 0;
dp[1] = 0;

for (int i = 2; i <= n; i++) {
    // 有选择！比较两种走法哪个更便宜
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}

这里就有“选择”了：要从i-1过来还是从i-2过来？选花费更小的那个。

三、什么时候用递推，什么时候用DP？

问题特征	用什么	例子
结果唯一，按公式直接推	递推	斐波那契、阶乘、前缀和
有多种选择，要挑最优	动态规划	背包、最短路径、最小花费
求“有多少种方案”	都可以（通常是DP）	爬楼梯、路径计数

四、经典例子对比

递推经典：兔子繁殖（斐波那契）

// 没有选择，就是 F(n) = F(n-1) + F(n-2)
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++) {
    f[i] = f[i-1] + f[i-2];
}

DP经典：01背包

// 每个物品：拿或不拿，两种选择，选价值更大的
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

五、总结表

	递推	动态规划
有没有选择	没有	有（max/min）
状态转移	`dp[i] = f(dp[i-1])`	`dp[i] = max/min(...)`
复杂度	O(n) 通常	O(n²) 或更高
典型应用	斐波那契、阶乘	背包、LIS、编辑距离