leetcode-70 爬楼梯(java实现)

爬楼梯

• 题目
• 分析1 递归写法
• 动态规划解法

题目

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

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

分析1 递归写法

如果要爬上第n阶，要么是从第n-1上面再爬1阶上去的，要么是从n-2上面再爬2阶上去的，那么我们就可以想到 f(n) = f(n-1)+f(n-2),这样也就很容易利用递归写出来

public static int climbStairs(int n) {

        // 这个貌似也是要用到递归，把之前的n-1个台阶的步骤全部加起来就可以了
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }

递归树的高度为n，每个节点有2个子节点，所以总共需要计算的节点数为2的n次方。因此，时间复杂度为O(2^n)
空间复杂度也比较高，因为每个递归函数调用都会创建一个新的栈帧，占用一定的内存。递归树的深度为n，所以空间复杂度为O(n)。

提交后，leetcode 平台提示运行失败，超时了

本地是能正常输出的，写法和思路是没有问题的，不过确实慢

动态规划解法

假设到达第i个楼梯的不同方法数为dp[i]，则有以下递推式：

dp[i] = dp[i-1] + dp[i-2]

因为每次只能爬1个或2个楼梯，所以到达第i个楼梯的方法数等于到达第i-1个楼梯的方法数加上到达第i-2个楼梯的方法数。

初始状态为dp[1]=1和dp[2]=2，因为到达第1个楼梯只有1种方法，到达第2个楼梯有2种方法（一次跨2个或者分两次跨1个）。

最终要求的答案是到达第n个楼梯的方法数，即dp[n]。

public int climbStairs(int n) {
    if (n == 1) return 1;
    // 当需要计算到 dp[n] 时，数组下标是从 0 到 n 的，需要定义一个长度为 n+1 的数组才能存储计算结果。如果定义一个长度为 n 的数组，那么在计算 dp[n] 的时候，就会发生数组越界的错误
    int[] dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

时间复杂度为O(n)，空间复杂度为O(n)。

提交后的结果成功