70. 爬楼梯(Climbing Stairs)E

英文题目

• 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?

• Example 1:

• Input: 2
  Output: 2
  Explanation: There are two ways to climb to the top.
  1. 1 step + 1 step
  2. 2 steps
  

• Example 2:

• Input: 3
  Output: 3
  Explanation: There are three ways to climb to the top.
  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step
  

• Constraints:

• 1 <= n <= 45

中文题目

• 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

• 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

• 注意：给定 n 是一个正整数。

• 示例 1：

• 输入： 2
  输出： 2
  解释： 有两种方法可以爬到楼顶。
  1.  1 阶 + 1 阶
  2.  2 阶
  

• 示例 2：

• 输入： 3
  输出： 3
  解释： 有三种方法可以爬到楼顶。
  1.  1 阶 + 1 阶 + 1 阶
  2.  1 阶 + 2 阶
  3.  2 阶 + 1 阶
  

动态规划

• 其实就是动态规划问题，斐波那契

• 用表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，可列出如下式子：

• 意味着爬到第 x 级台阶的方案数是爬到第 x - 1 级台阶的方案数和爬到第 x - 2 级台阶的方案数的和

  # python3: 时间 36 ms, 击败 83.11%; 内存 15.9 MB, 击败 58.72%
  class Solution:
      def climbStairs(self, n: int) -> int:
          if n <= 2:
              return n
          prev, curr = 1, 2
          for _ in range(3, n+1):
              prev, curr = curr, prev + curr
          return curr
  

  // c++: 时间 4 ms, 击败 24.60%; 内存 5.8 MB, 击败 66.65%
  class Solution {
  public:
      int climbStairs(int n) {
          if (n <= 2) {
              return n;
          }
          int prev = 1, curr = 2;
          for (int i = 3; i <= n; ++i) {
              int next = prev + curr;
              prev = curr;
              curr = next;
          }
          return curr;
      }
  };
  

  // java: 时间 0 ms, 击败 100%; 内存 38 MB, 击败 85.90%
  class Solution {
      public int climbStairs(int n) {
          if (n <= 2) {
              return n;
          }
          int prev = 1, curr = 2;
          for (int i = 3; i <= n; ++i) {
              int next = prev + curr;
              prev = curr;
              curr = next;
          }
          return curr;
      }
  }
  

  // go: 时间 0 ms, 击败 100%; 内存 1.7 MB, 击败 99.87%
  func climbStairs(n int) int {
      if n <= 2 {
          return n
      }
      prev, curr := 1, 2
      for i := 3; i <= n; i++ {
          prev, curr = curr, prev + curr
      }
      return curr
  }
  

  // javascript: 时间 60 ms, 击败 62.66%; 内存 40.8 MB, 击败 57.79%
  /**
   * @param {number} n
   * @return {number}
   */
  var climbStairs = function(n) {
      if (n <= 2) {
          return n;
      }
      let prev = 1, curr = 2;
      for (let i = 3; i <= n; ++i) {
          let next = prev + curr;
          prev = curr;
          curr = next;
      }
      return curr;
  };