LeetCode Climbing Stairs JAVA

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?

简单分析一下，如果我第一步走了一步，那么剩下来就是f（n-1）；如果我第一步走了两步，那么剩下来的就是f（n-2）。如果总共只有1个台阶，那么就一种走法，如果总共只有两个台阶，那么有两种走法。因此很简单就想到了可以用斐波那契来做，整个算法用递归，还是很简单就可以实现了的。代码如下：

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

自己随便设置了几个参数跑了一下，结果是没得问题的。然后就提交啦。结果。。。。

当入参比较大的时候。这时候递归算法就太耗费时间了。超时了。所以只能采取比较笨的循环方式了，算法如下：

public class Solution {
    public int climbStairs(int n) {
        int f1 = 1;
        int f2 = 2;
        int f3 = 0;
        for(int i = 1; i < n; i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
}
           

这次accept了。在网上搜索了一下，还有人用矩阵实现，算法复杂度更低了好多。感兴趣的可以自己学习一下。