1, 题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. #python
  2. object Solution {
  3.     def climbStairs(n: Int): Int = {
  4.         if (n < 3) {
  5.             return n
  6.         }
  7.         var fn1 = 1
  8.         var fn2 = 2
  9.         var fn = 0
  10.         for (i <- 3 to n) {
  11.             fn = fn1 + fn2
  12.             fn1 = fn2
  13.             fn2 = fn
  14.         }
  15.         fn
  16.     }
  17. }
  1. #python
  2. class Solution:
  3.     def climbStairs(self, n: int) -> int:
  4.         if n < 3:
  5.             return n
  6.         a, b = 1, 2
  7.         for i in range(2, n):
  8.             fn = a + b
  9.             a, b = b, fn
  10.         return fn