每日题解:LeetCode 70. 爬楼梯

Author Avatar
清水雅然君 06月 13,2020

题目地址
个人博客地址

题目描述

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

解法

JAVA

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        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];
    }
}

解题思路

DP(动态规划)

我们用 f(x)表示我们的处第x台阶的方法总数,由于每次你可以爬 1 或 2 个台阶,所以我们可以得出状态公式为:

f(x) = f(x - 1) + f(x - 2)
其实,我们从举例中,可以得出答案是一个斐波那契数列,假设DP[x],为第x层的方法数,
//避免出现下标越界问题,给数据长度加1
    int[] dp = new int[n + 1];
    //由于我们将从i-2开始计算,先将1,2下标先赋值,遍历下标从3开始
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

以上写的,使用了数组,我们的空间复杂度为O(n)。可以使用两个变量一个记录i-2的值,一个记录i-1的值,使得时间复杂度降低到O(1)

 int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;