资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

递归 vs 动态规划：算法题中的选择与优化

创作时间:

作者:

@小白创作中心

递归 vs 动态规划：算法题中的选择与优化

引用

来源

https://juejin.cn/post/7445661526369288207

递归和动态规划是算法设计中的两种重要方法，它们在解决复杂问题时各有优势。本文通过两个经典的LeetCode题目——爬楼梯和零钱兑换，深入讲解了递归和动态规划的原理、实现方式以及优化技巧。通过对比分析，帮助读者理解这两种方法的特点和适用场景，从而在实际问题中做出更合适的选择。

引言

在解决复杂算法问题时，递归和动态规划是两种强大的工具，它们能够帮助我们高效地处理问题。让我们通过leetcode的两道算法题，深入探索这两种方法，解锁算法解题的新境界。

一、爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

来自leetcode热题100道第70题：leetcode.cn/problems/cl…

看到这道题，我们先想到的肯定是递归

先把问题定位到终点
站在终点，思考后退的各种可能性
自顶向下，画树状结构的图

思考完毕就该实践了。

解法一：暴力递归

const climbStairs = function(n) {
    if(n <=2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
};
console.log("开始爬");
console.time("climbStairs");
console.log(climbStairs(50));
console.log("爬完了");
console.timeEnd("climbStairs");

可以看到，计算50个楼梯用了足足一分半的时间，显然暴力递归存在缺陷，具体有哪些：

重复计算:相同的子问题会被多次计算。例如，在计算
f(50)
时，
f(49)
和
f(48)
都会被计算，而在计算
f(49)
时，
f(48)
又会被再次计算。这种重复计算会导致算法效率极低，尤其是当
n
较大时，计算量会呈指数级增长。
时间复杂度:暴力递归的时间复杂度是指数级的，具体来说是 O(2^n)。这是因为每个递归调用都会分裂为两个新的递归调用（
f(n) = f(n-1) + f(n-2)
），导致递归树的节点数呈指数增长。
空间复杂度:虽然暴力递归的空间复杂度是 O(n)，因为递归调用栈的深度最多为
n
，但当我们使用记忆化递归或动态规划时，空间复杂度仍然保持为 O(n)，因为我们需要存储中间结果。
当n很大的时候，会导致栈溢出:当
n
非常大时，递归调用的深度可能会超过系统的栈大小限制，导致栈溢出错误。

该如何优化

解法二：记忆化递归

const f = [];//某层结果和数组的下标一一对应
const climbStairs = function(n) {
    if(n <= 2) return n;
    if(f[n]===undefined)
        f[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return f[n];
};
console.log("开始爬");
console.time("climbStairs");
console.log(climbStairs(50));
console.log("爬完了");
console.timeEnd("climbStairs");

记忆化递归是一种优化技术，用于加速递归算法的执行。它通过将已经计算过的子问题的结果存储起来，避免了重复计算相同的子问题。简单来说就是用空间换时间，可以看到计算50个楼梯仅仅用了1.2ms。那么这个方法就是最优解了吗？我们也说到了记忆化递归是拿空间换时间，所以它的空间开销是很大的。

换一种思路，能用递归的问题，一定可以用动态规划解决。

解法三：动态规划(dp)

const climbStairs = function(n) {
const f = []; // f[i] 表示爬到第i层的方法数
f[1] = 1;
f[2] = 2;
// 迭代  从3开始
for(let i =3;i<=n;i++){
f[i] = f[i-1]+f[i-2];
}
return f[n];
}
console.log("开始爬");
console.time("climbStairs");
console.log(climbStairs(50));
console.log("爬完了");
console.timeEnd("climbStairs");

动态规划(dp)是一种用于解决优化问题的算法设计技术，特别适用于那些可以通过将问题分解为更小的、相似子问题来求解的问题。动态规划的核心思想是避免重复计算，通过存储已经计算过的子问题的结果，从而提高算法的效率。可以看到，使用动态规划计算爬50级楼梯比记忆化递归还少了一半多的时间。

为什么使用动态规划能这么快？

迭代实现：动态规划使用迭代而不是递归，避免了函数调用栈的开销，并且更符合现代计算机的缓存机制。
连续内存访问：动态规划的迭代实现通常具有良好的空间局部性，能够充分利用 CPU 缓存，减少内存访问的时间。
显式初始化：动态规划在开始时就显式地初始化所有必要的边界条件，减少了冗余计算和检查。
空间优化：动态规划更容易进行空间优化，如使用滚动数组等技巧，进一步提高了效率。
并行化潜力：动态规划的迭代实现通常具有较低的数据依赖性，适合并行计算框架。

那么动态规划就一定比记忆化递归好吗？

不关心具体过程：不能打印具体的过程(路径)，只得到达成某个目的的解法个数。
实现难度较高：需要手动设计状态转移方程，并且要确保状态之间的依赖关系正确无误。对于复杂的多维问题，动态规划的实现可能会变得非常复杂。
容易出错：由于需要手动管理状态转移和填表过程，动态规划的实现容易出现逻辑错误，特别是在处理边界条件时。

二、硬币兑换问题(动态规划升级版)

给你一个整数数组
coins
，表示不同面额的硬币；以及一个整数
amount
，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回
-1
。你可以认为每种硬币的数量是无限的。

来自leetcode的题库322题：leetcode.cn/problems/co…

const coinChange = function(coins, amount) {
    const f = []; // 每个面值的最小硬币个数
    f[0] = 0;//初始值
    // 迭代 从1开始
    for(let i = 1;i<=amount;i++){
        f[i] = Infinity;// 无限大
        // 求最小值
        // i 表示当前金额  f[i]表示当前金额的最小硬币个数
        // coins[j]表示最后一枚硬币的面值
        for(let j = 0;j<coins.length;j++){
            if(i - coins[j] >= 0){
                f[i] = Math.min(f[i],f[i - coins[j]] + 1);
            }
        }
    }
    if(f[amount] === Infinity) 
        return -1;
    return f[amount];
 }
console.log(coinChange([1,2,5],11))

动态规划是解决零钱兑换问题的有效方法，通过自底向上的方式逐步构建出所有子问题的解，最终得到原问题的解。这个问题就比上面爬楼梯的问题复杂了许多。

代码解释

初始化：

f[0] = 0
：表示凑成金额为0需要0个硬币。
f[i] = Infinity
：对于每个
i
，初始时将其设为无穷大，表示尚未找到解。

外层循环：

for (let i = 1; i <= amount; i++)
：从1开始，逐步计算每个金额
i
所需的最少硬币个数。

内层循环：

for (let j = 0; j < coins.length; j++)
：遍历所有硬币面值
coins[j]
。
if (i - coins[j] >= 0)
：确保当前金额
i
至少可以减去某个硬币面值
coins[j]
。
f[i] = Math.min(f[i], f[i - coins[j]] + 1)
：更新
f[i]
，表示凑成金额
i
的最小硬币个数。这里使用了状态转移方程
f[i] = min(f[i], f[i - coins[j]] + 1)
，即当前金额
i
的最小硬币个数等于
i - coins[j]
的最小硬币个数加上1。