题目

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

代码

class Solution {

public:

    int climbStairs(int n) {

        //1 1  1种

        //2 1+1 2   2种

        //3 1+1+1 1+2 2+1   3种

        //4 1+1+1+1 2+2 2+1+1 1+2+1 1+1+2   5种

        //5 1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 2+2+1 2+1+2 1+2+2 8种

        //规律如下

        //1-1 2-2 3-3 4-5 5-8 6-13 当前层等于前两层之和

        if(n==1)

            return 1;

        if(n==2)

            return 2;

        int firstNum=1,secNum=2,result=0;

        for(int i=3;i<=n;i++)

        {

            result=firstNum+secNum;

            firstNum=secNum;

            secNum=result;

        }

        return result;

    }

};

巴特西

[LeetCode]爬楼梯

题目

代码

最新文章

热门文章