首页 > itarticle > [leetcode]climbing stairs

[leetcode]climbing stairs

admin 11月 12, 2020 0

题目描述

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?

解题思路与代码

该题本质上是斐波那契数列，代码如下：

public class  {
    
    // public int climbStairs(int n) {
    //     if(n == 1) return 1;
    //     if(n == 2) return 2;
    //     return climbStairs(n-1) + climbStairs(n-2);
    // }

    // public int climbStairs(int n){
    //     if(n <= 0) return 0;
    //     if(n == 1) return 1;
    //     if(n == 2) return 2;
    //   int[] res = new int[n+1];
    //   res[1] = 1;
    //   res[2] = 2;
    //   for(int i = 3;i <= n;i++){
    //       res[i] = res[i-2] + res[i-1];
    //   }
    //     return res[n];
    // }

    public int climbStairs(int n){
        if(n <= 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        //前一级阶梯不同路径数
        int oneStep = 2;
        //前两级阶梯的不同路径数
        int twoStep = 1;

        int allWays = 0;
        for(int i = 3;i <= n; i++){
            allWays = oneStep + twoStep;
            twoStep = oneStep;
            oneStep = allWays;
        }
        return allWays;
    }
}