跳转至

LeetCode: 70. 爬楼梯

1、题目描述

假设你正在爬楼梯。需要 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 步

2、解题思路

​ 爬楼梯实际是一个斐波那切数列

​ 可以这样考虑,如果是n级台阶的所有走法,那么第一步可以是1步,剩余n-1级,也可以是2步,剩余n-2级

​ 因此,S(n) = S(n-1)+S(n-2)

​ S(0) = 1

​ S(1) = 1

​ S(2) = 2

​ S(3) = 3

...

int climbStairs(int n) {
    if (n == 0) {
        return 0;
    }
    int a = 1;
    int b = 1;
    int temp = a;
    for (int i = 0; i < n; i++) {
        temp = a;
        a = b;
        b = temp+b;
    }
    return a;
}