[NC]68 爬楼梯、丢手绢

Copy of [LeetCode]Dp70 爬楼梯、丢手绢

🚩传送门：https://leetcode-cn.com/problems/climbing-stairs/

题目

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

解题思路：动态规划

我们用 表示爬到第 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

意味着爬到第 级台阶的方案数是爬到第 级台阶和爬到第 级台阶的方案数的和。

复杂度分析

时间复杂度：，其中 为楼梯长度 。
空间复杂度：，需要维护 Dp 数组空间。

代码

我的代码

public class Demo {
    //动态规划 dp[i]=dp[i-1]+dp[i-2];
    public static int climbStairs_0(int n) {
        int[]dp=new int[n+1];//使n和dp[n]对应
        dp[0]=1;dp[1]=1;
        for (int i = 2; i <=n ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println(climbStairs(10));
    }
}

解题思路：滚动数组

动态规划数组空间浪费严重，因此可以用滚动数组思想来节省空间

复杂度分析

时间复杂度：，其中 为楼梯长度 。
空间复杂度：，需要维护常数空间。

代码

我的代码

public class Demo {
    //滚动数组,只需要3个变量
    //  res =     y     +     x
    //dp[i] = dp[i - 1] + dp[i - 2]
    public int climbStairs(int n) {
        int x=1,y=1,res=1;
        for(int i=2;i<=n;i++){
            res=x+y;
            x=y;y=res;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(climbStairs(10));
    }
}