Fork me on GitHub

LeetCode-070-爬楼梯

发表于

题目描述

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

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

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

示例

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

思路

迭代法解决
设S(n)表示走n级台阶的走法数量。走n级台阶，第一步只有两种选择：可以选择走1阶，然后还有S(n-1)种走法；选择走2阶，那么接下来有S(n-2)种走法。那么S(n) = S(n-1) + S(n-2)。

解答

1
2
3
4
5
6
7
8
9
10
11
12
public int climbStairs(int n) {
        if (n<2){
            return n;
        }
        int f1 = 1,f2 = 0,sum = 0;
        for (int i=1;i<=n;i++){
            sum = f1+f2;
            f2 =f1;
            f1 = sum;
        }
        return sum;
    }