首页 Java🎯,LeetCode🚀

LeetCode-70-爬楼梯

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

解题思路

方法1、动态规划:

当n等于1的时候,只需要跳一次即可,只有一种跳法,记f(1)=1

当n等于2的时候,可以先跳一级再跳一级,或者直接跳二级,共有2种跳法,记f(2)=2

当n等于3的时候,他可以从一级台阶上跳两步上来,也可以从二级台阶上跳一步上来,所以总共有f(3)=f(2)+f(1);

所以当等于n(n>2)的时候,总共有f(n)=f(n-1)+f(n-2)种跳法

此时的状态: 为n的时候,可能的跳法有多少种

状态转移方程:f(n)=f(n-1)+f(n-2)

方法2、优化的动态规划:

上一个方法需要开辟一个n的数组,其实可以直接用双指针完成状态的转移,不再需要开辟多余的空间

Java代码

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];
    }
}

Java代码2

class Solution {
    public int climbStairs(int n) {
        int[] result = new int[]{1, 1};
        if (n < 2) {
            return result[n];
        }
        int sum = 0;
        int f1 = 1;
        int f2 = 1;
        for (int i = 2; i <= n; i++) {
            sum = (f1 + f2);
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }
}



文章评论

目录