// @Title: 爬楼梯 (Climbing Stairs)
// @Author: qisiii
// @Date: 2020-04-15 10:24:17
// @Runtime: 0 ms
// @Memory: 35.3 MB
// @comment: 
// @flag: 
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];
    }}

// @Title: 爬楼梯 (Climbing Stairs)
// @Author: qisiii
// @Date: 2020-04-15 10:28:41
// @Runtime: 0 ms
// @Memory: 35.6 MB
// @comment: 
// @flag: 
class Solution {
    public int climbStairs(int n) {
        int first=1;
        int second=2;
        if(n==1)
        return first;
        for(int i=3;i<=n;i++){
            int third=first+second;
            first=second;
            second=third;
        }
        return second;
    }
    }

// @Title: 爬楼梯 (Climbing Stairs)
// @Author: qisiii
// @Date: 2022-03-10 12:41:45
// @Runtime: 0 ms
// @Memory: 38 MB
// @comment: 普通动态规划
// @flag: BLUE
class Solution {
    public int climbStairs(int n) {
        if(n<2){
            return 1;
        }
        int[] dp=new int[n+1];
        dp[0]=1;dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

// @Title: 爬楼梯 (Climbing Stairs)
// @Author: qisiii
// @Date: 2022-03-10 12:44:55
// @Runtime: 0 ms
// @Memory: 38.1 MB
// @comment: 因为只有前后脚，所以可以使用三个变量来控制
// @flag: BLUE
class Solution {
    public int climbStairs(int n) {
        if(n<2){
            return 1;
        }
        int s=0,t=1,r=1;
        for(int i=2;i<=n;i++){
            s=t+r;
            r=t;
            t=s;
        }
        return s;
    }
}

// @Title: 爬楼梯 (Climbing Stairs)
// @Author: qisiii
// @Date: 2024-09-22 22:33:34
// @Runtime: 0 ms
// @Memory: 39.4 MB
// @comment: 
// @flag: 
class Solution {
    public int climbStairs(int n) {
        if(n<=2){
            return n;
        }
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        //dp[n]=dp[n-1]+dp[n-2];
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}