Philip

Philip's blog

0%

algorithm-dp-climb-stairs

Posted on Edited on In
Symbols count in article: 1.1k Reading time ≈ 4 mins.

问题描述

一座楼梯有n个台阶，每一步可以走一个台阶，也可以走两个台阶，请问走完这座楼梯共有多少种方法?

这是一个经典的问题，俗称走台阶问题，此题有多种解法，我们分别看看每种解法的优劣。我们现推理一下递推关系，假设f(n)表示走n个台阶的方法数，那么：

  1. 当n = 1时，只有一种走法，即f(1) = 1
  2. 当n = 2时，有两种走法（每次走一个台阶:1-1，或者一次走两个台阶：2），即f(2) = 2
  3. 当n = 3时，有三种走法（1-1-1，1-2，2-1），即f(3) = 3
  4. 当n = n时，如果第一步走一个台阶，剩下n-1个台阶，有f(n-1)种走法；如果第一步走两个台阶，剩下n-2个台阶，有f(n-2)种走法，所以f(n) = f(n-1) + f(n-2)

递归解法

根据上面的递推关系，我们很容易写出递归解法，代码如下：

1
2
3
4
5
6
7
function climbStairs(n) {
  if (n <= 2) {
    return n;
  } else {
    return climbStairs(n - 1) + climbStairs(n - 2);
  }
}

递归法虽好，但是效率极其低下，当n = 100时，程序就卡死了，我们来分析一下时间复杂度，当计算f(n)时，需要计算f(n-1)和f(n-2)，而计算f(n-1)时，需要计算f(n-2)和f(n-3)，依次类推，可以构造一个递归二叉树，其根节点是f(n)，左子树是f(n-1)，右子树是f(n-2)，左子树的左子树是f(n-2)，右子树是f(n-3)，以此类推，可以看出，递归法的时间复杂度是指数级别的，即O(2^n)。

以n = 5为例，递归树如下：这里面f(3)被计算了2次，f(2)被计算了3次，f(1)被计算了2次。

1
2
3
4
5
6
7
         f(5)
        /    \
     f(4)    f(3)
     /  \    /  \
  f(3) f(2) f(2) f(1)
  /  \
f(2) f(1)

由于每个子问题被计算多次，所以这里面有大量的重复计算，为了避免重复计算，我们可以将计算过的结果存储起来，下次用到的时候直接使用存储的结果即可。这就是记忆化搜索（备忘录）方法。

记忆化搜索(备忘录)解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function climbStairs(n, memory = []) {
  if (n <= 2) {
    return n;
  } else {
    // 如果计算过，直接使用存储的结果
    if (memory[n] !== undefined) {
      return memory[n];
    } else {
      // 计算并存储，不能直接return，必须先存放到memory[n]中
      memory[n] = climbStairs(n - 1, memory) + climbStairs(n - 2, memory);
      return memory[n];
    }
  }
}

使用记忆化搜索后，每个子问题只会被计算一次，时间复杂度降为O(n)，空间复杂度为O(n)。空间复杂度就是memory数组的长度。

动态规划解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function climbStairs1(n) {
  // 如果台阶数小于等于2，直接返回n（因为1阶有1种方法，2阶有2种方法）
  if (n <= 2) return n;

  // 定义一个数组dp，其中dp[i]表示到达第i个台阶的方法数
  let dp = new Array(n + 1);
  dp[0] = 0; // 第0阶没有意义，设为0
  dp[1] = 1; // 到达第1阶只有1种方法
  dp[2] = 2; // 到达第2阶有2种方法

  // 动态规划填表
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  // 返回到达第n阶的方法数
  return dp[n];
}

还能进一步优化吗?上面的空间复杂度是O(n)，我们可以看到，计算f(n)时只需要f(n-1)和f(n-2)的结果，所以我们只需要存储f(n-1)和f(n-2)的结果即可，不需要存储所有的结果。我们用两个变量来存储f(n-1)和f(n-2)的结果，然后依次计算f(n)，这就是迭代法。

动态规划解法（优化空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function climbStairs(n) {
  if (n <= 2) {
    return n;
  } else {
    let prev1 = 1;
    let prev2 = 2;
    let current = 0;

    for (let i = 3; i <= n; i++) {
      current = prev1 + prev2;
      prev1 = prev2;
      prev2 = current;
    }

    return current;
  }
}

迭代法的时间复杂度是O(n)，空间复杂度是O(1)。因为只使用了三个变量，所以空间复杂度是常数级别的。

打印出所有走法

我们稍微拓展一下，如果想打印出所有的走法，该怎么做呢？

1

总结

时间复杂度和空间复杂度总结如下表：

方法 时间复杂度 空间复杂度
递归 O(2^n) O(n)
记忆化搜索 O(n) O(n)
动态规划 O(n) O(n)
动态规划（优化空间） O(n) O(1)