介绍

有 n 个楼梯，一个站在底部的人想到达顶部。这个人可以一次爬 1 个楼梯或 2 个楼梯。数一数这个人有多少种方法可以到达顶层。

方案

递归法

这种方法的表达式为：

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

上述表达式实际上是斐波那契数（Fibonacci numbers）的表达式，但有一点需要注意，way (n) 的值等于 fibonacci(n+1) 。

ways(1) = fib(2) = 1
ways(2) = fib(3) = 2
ways(3) = fib(4) = 3

实现：

// A simple recursive function to find n'th fibonacci number
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
 
// Returns number of ways to reach s'th stair
function countWays(s) {
  return fib(s + 1);
}

复杂度：

• 时间复杂度： O(2^n) 。由于冗余计算，上述实现的时间复杂度是指数级的（黄金分割率（golden ratio）提高到 n 次方）。使用斐波那契函数优化，它可以在 O（logn）时间内工作。
• 空间复杂度： O(1) 。

问题的一般化

例如，如果 m 是 4，这个人每次可以爬 1 个楼梯或 2 个楼梯或 3 个楼梯或 4 个楼梯，如何计算这个人可以爬到 m 个楼梯的方式。

对于上述方法的一般化，可以使用以下递归关系： ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... ways(n-m, m) 。

实现：

// A recursive function used by countWays
function countWaysUtil(n, m) {
  if (n <= 1) return n;
  let res = 0;
  for (let i = 1; i <= m && i <= n; i++) res += countWaysUtil(n - i, m);
  return res;
}
 
// Returns number of ways to reach s'th stair
function countWays(s, m) {
  return countWaysUtil(s + 1, m);
}

缓存法

我们也可以使用 dp 的自下而上的方法来解决这个问题，为此，我们可以创建一个数组 dp []，并将其初始化为 - 1。每当我们看到一个子问题没有得到解决，我们就可以调用递归方法。否则，如果子问题已经解决了，我们就停止递归。

实现：

// A simple recursive program to find N'th fibonacci number
function fib(n, dp) {
  if (n <= 1) return dp[n] = 1;
  if(dp[n] != -1 ) { return dp[n]; }
  dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
  return dp[n] ;
}
 
// Returns number of ways to reach s'th stair
function countWays(n) {
  let dp = new Array(n+1).fill(-1) ;
  fib(n, dp);
  return dp[n] ;
}

复杂度分析：

• 时间复杂度：O (n)
• 辅助空间：O (n)

动态规划

我们用以下关系自下而上地创建一个表 res []， res[i] = res[i] + res[i-j] for every (i-j) >= 0 。这样，数组的第 i 个索引将包含考虑到所有攀登的可能性（即从 1 到 i），到达第 i 个步骤所需的方法数。

实现：

 
// A recursive function used by countWays
function countWaysUtil(n, m) {
  let res = [];
  res[0] = 1;
  res[1] = 1;
  for (let i = 2; i < n; i++) {
    res[i] = 0;
    for (let j = 1; j <= m && j <= i; j++) res[i] += res[i - j];
  }
  return res[n - 1];
}
 
// Returns number of ways to reach s'th stair
function countWays(s, m) {
  return countWaysUtil(s + 1, m);
}

复杂度分析：

• 时间复杂度： O(m*n)
• 辅助空间： O(n)

优化空间的动态规划

在这种方法中，我们可以通过不使用任何额外的空间来优化 DP 方法。首先，我们可以创建两个变量 prev 和 prev2 来存储爬一个楼梯或两个楼梯的方法数量。然后，我们可以运行一个 for 循环来计算到达顶部的方法总数。下面是上述想法的代码实现：

int countWays(int n) {
  // declaring  two variables to store the count
  int prev = 1;
  int prev2 = 1;
  // Running for loop to count all possible ways
  for (int i = 2; i <= n; i++) {
    int curr = prev + prev2;
    prev2 = prev;
    prev = curr;
  }
  return prev;
}

JavaScript：

/**
 * @function ClimbStairs
 * @description You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 * @param {Integer} n - The input integer
 * @return {Integer} distinct ways can you climb to the top.
 * @see [Climb_Stairs](https://www.geeksforgeeks.org/count-ways-reach-nth-stair/)
 */

const climbStairs = (n) => {
  let prev = 0
  let cur = 1
  let temp

  for (let i = 0; i < n; i++) {
    temp = prev
    prev = cur
    cur += temp
  }
  return cur
}

复杂度分析：

• 时间复杂度：O (n)
• 空间复杂度：O (1)

滑窗法

这种方法有效地实现了上述 DP 方法。在这个方法中，对于第 1 个楼梯，我们保持一个窗口，即最后 m 个可能的楼梯的总和，我们可以从中爬到第 1 个楼梯。我们不运行内循环，而是将内循环的结果保存在一个临时变量中。我们删除前一个窗口的元素，加入当前窗口的元素并更新总和。

实现：

// Returns number of ways
// to reach s'th stair
function countWays(n , m) {
  const res = Array(n + 1).fill(0);
  let temp = 0;
  res[0] = 1;

  for (i = 1; i <= n; i++) {
    const s = i - m - 1;
    const e = i - 1;
    if (s >= 0) {
      temp -= res[s];
    }
    temp += res[e];
    res[i] = temp;
  }
  return res[n];
}

复杂度分析：

• 时间复杂度：O (n)
• 辅助空间：O (n)

数学公式法

这只适用于这个问题，如果（计算步骤中顺序并不重要）。在这种方法中，我们只需计算有 2 的集合的数量。顺序不重要是指对于 n = 4， {1 2 1}，{2 1 1}。 ,{2 1 1} ，{1 1 2} 被认为是相同的。

// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
parseInt(1 + (n / 2)); 

复杂度分析：

• 时间复杂度：O (1)
• 空间复杂度：O (1)

参考

• Count ways to reach the n'th stair - GeeksforGeeks (opens new window)