LeetCode之76题爬楼梯

来源：力扣（LeetCode）https://leetcode-cn.com/problems/climbing-stairs

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

示例：

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

这道题类似斐波那契数列

Java版

动态规划

当我们要爬到第n阶楼梯时，有2种方式上去，就是从第n-1阶走1阶上去或者是n-2阶走2阶上去。由此得出推导公式：dp[n]=dp[n-1]+dp[n-2]

public int climbStairs(int n) {
    if(n<2){
        return n;
    }

// 因为我们只需要前面2个的值，因此可以不用数组来记录，以此来节约空间    
//        int[] dp = new int[n+1];
//        // dp[n] = dp[n-1]+dp[n-2]
//        for(int i=1; i<=n; i++){
//            if(i-1>0 && i-2>0){
//                dp[i] = dp[i-1]+dp[i-2];
//            }else{
//                dp[i] = i==1?1:2;
//            }
//        }
//        return dp[n];

    int dp1 = 0;
    int dp2 = 0;
    int dp = 1;
    for(int i=1; i<=n; i++){
        dp2 = dp1;
        dp1 = dp;
        dp = dp1+dp2;
    }
    return dp;
}

通过公式直接计算

这个就是存数学的，去复习一下线性代数就很好理解了。

public int climbStairs(int n) {
    double sqrt5 = Math.sqrt(5);
    double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
    return (int) Math.round(fibn / sqrt5);
}