Dynamic Programming

动态规划定义

动态规划主要是对普通递归的一种优化。每当我们看到递归解决方案对相同输入进行了重复调用时，我们就可以使用动态规划来优化它。这个想法是简单地存储子问题的结果，这样当后续需要时就不必重新计算它们。这种简单的优化通常将时间复杂度从指数型减少到多项式型。

如何工作的

识别子问题：将主要问题划分为更小的独立子问题。
存储解决方案：解决每个子问题，并将解决方案存储在表格或数组中。
构建解决方案：利用存储的解决方案构建主要问题的解决方案。
避免冗余：通过存储解决方案，动态规划确保每个子问题只解决一次，从而减少计算时间。

从爬楼梯问题开始

当我们在爬楼梯时，假设每层楼有 n 级台阶，那么我们每次可以爬 1 级或 2 级台阶。那么我们爬到第 n 级台阶有多少种方法呢？

比如我们有 10 级台阶

0-1 1种（1步） 0-2 2种（1步+1步，2步） 0-3 3种（1步+1步+1步，1步+2步，2步+1步） 0-4 5种（1步+1步+1步+1步，1步+1步+2步，1步+2步+1步，2步+1步+1步，2步+2步） …

我们可以发现一个规律，那就是 f(n) = f(n-1) + f(n-2)，这就是一个典型的动态规划问题。

// 到达第4级台阶的所有可能方法

// 情况1：从第3级台阶走1步上来
1) 1 + 1 + 1 + 1  // 到达第3级的方法之一，然后走1步
2) 1 + 2 + 1      // 到达第3级的方法之一，然后走1步
3) 2 + 1 + 1      // 到达第3级的方法之一，然后走1步

// 情况2：从第2级台阶走2步上来
4) 1 + 1 + 2      // 到达第2级的方法之一，然后走2步
5) 2 + 2          // 到达第2级的方法之一，然后走2步

// 总结：
// 到达第3级台阶有3种方法，每种后面加1步 = 3种方法
// 到达第2级台阶有2种方法，每种后面加2步 = 2种方法
// 所以总共有 3 + 2 = 5种方法

因此，我们可以写出递归公式：

f(n) = f(n-1) + f(n-2)

现在我们用动态规划来解决一个求n个台阶有多少种走法的问题。

function climbStairsDP(n) {
  const dp = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

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

function climbStairsRecursiveMemo(n) {
  const cache = {};
  function climb(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    if (cache[n]) return cache[n];
    cache[n] = climb(n - 1) + climb(n - 2);
    return cache[n];
  }
  return climb(n);
}

function main() {
  console.log(climbStairsDP(1)); // 1
  console.log(climbStairsDP(2)); // 2
  console.log(climbStairsDP(3)); // 3
  console.log(climbStairsDP(4)); // 5
  console.log(climbStairsDP(10)); // 89
}

main();

function benchmark() {
  {
    const start = performance.now();
    const result = climbStairsDP(40);
    const end = performance.now();
    console.log(`DP: ${end - start}ms, result: ${result}`); // 0.01ms, result: 165580141
  }
  {
    const start = performance.now();
    const result = climbStairsRecursive(40);
    const end = performance.now();
    console.log(`Recursive: ${end - start}ms, result: ${result}`); // 872.14ms, result: 165580141
  }
  {
    const start = performance.now();
    const result = climbStairsRecursiveMemo(40);
    const end = performance.now();
    console.log(`RecursiveMemo: ${end - start}ms, result: ${result}`); // 0.11ms, result: 165580141
  }
}

benchmark();

如果用普通递归，不进行DP优化的方式来解决这个问题，那么时间复杂度是指数级的，因为每次递归都会产生两个子问题，而每个子问题又会递归产生两个子问题，以此类推。颜色相同的节点表示相同的子问题，因此存在大量冗余计算。

参考：GeeksforGeeks - Dynamic Programming

动态规划定义

如何工作的

从爬楼梯问题开始

Read Next

Binary Search

Greedy Algorithm