从 DFS 到动态规划：算法优化思想的演进

在算法设计中，同一个问题往往可以用不同的方法求解。本文将以一个具体的例子，探讨从最基础的深度优先搜索（DFS）到动态规划的演进过程，分析每一步优化背后的思想。

从一个例子开始

让我们以经典的”爬楼梯”问题为例：假设你正在爬楼梯，每次可以爬 1 或 2 个台阶，请问爬到第 n 阶有多少种不同的方法？

方案一：朴素 DFS

最直观的解法是使用 DFS，把问题分解为更小的子问题：

function climbStairs(n) {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

这种方法的问题在于：

1. 存在大量重复计算
2. 时间复杂度为 O(2^n)，呈指数级增长
3. 当 n 较大时可能导致栈溢出

方案二：记忆化搜索

观察发现，DFS 过程中有许多子问题被重复计算。比如计算 f(5) 时，f(3) 会在计算 f(4) 和 f(5) 时各被计算一次。通过存储已计算的结果，我们可以避免重复计算：

function climbStairs(n, memo = new Map()) {
    if (n <= 1) return 1;
    if (memo.has(n)) return memo.get(n);
    
    const result = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    memo.set(n, result);
    return result;
}

优化效果：

1. 时间复杂度降至 O(n)
2. 空间复杂度为 O(n)
3. 保持了递归的清晰思路

方案三：动态规划

记忆化搜索本质上是”自顶向下”的解法。既然我们已经找到了子问题之间的关系，何不直接”自底向上”地构建解答？

function climbStairs(n) {
    const dp = new Array(n + 1);
    dp[0] = dp[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

这种方法的优势：

1. 避免了递归调用的开销
2. 代码更简洁，执行更高效
3. 便于理解和维护

方案四：空间优化

观察发现，在计算过程中，我们每次只需要用到最近的两个状态。因此可以只用两个变量来存储状态，进一步优化空间复杂度：

function climbStairs(n) {
    if (n <= 1) return 1;
    
    let prev = 1, curr = 1;
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
    
    return curr;
}

优化思想分析

这个演进过程展示了几个重要的算法设计思想：

1. 问题分解：

   • DFS 通过递归将问题分解为规模更小的子问题
   • 找到问题的最优子结构是后续优化的基础

2. 避免重复：

   • 记忆化搜索通过存储中间结果避免重复计算
   • 这种”以空间换时间”的思想是算法优化的常用手段

3. 方向转换：

   • 从”自顶向下”到”自底向上”的转变
   • 递推代替递归，往往能带来性能提升

4. 状态压缩：

   • 分析状态转移过程，只保留必要的状态
   • 这种思想在处理大规模数据时特别重要

总结与思考

从 DFS 到动态规划的演进，展示了算法优化的一般过程：

1. 先写出最直观的解法
2. 发现并消除重复计算
3. 寻找更优的求解方向
4. 优化空间使用

这个过程不仅适用于本例，也是解决其他算法问题的重要思路。关键是要善于发现问题中的重复计算，并找到优化的突破口。