目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs

2.思路

（1）动态规划
设 dp[i] 为走上第i级阶梯的走法，那么由题可知floor[1]=0（第1级阶梯为起点，不用走，所以其值为0），dp[2]=1，dp[3]=2，dp[4]=3，dp[5]=5，…，由此可以找出递推式dp[i]=dp[i-1]+dp[i-2]。
具体推理过程如下：假设现在按要求dp[i]（i>=3），通过分析可知通过一次跨楼梯到达第i级阶梯的方法有2种：
在第i-1级阶梯上跨一级或者在第i-2级阶梯上跨二级。
由前面的设定已知 dp[i-1] 为走上第 i-1 级阶梯的走法，dp[i-2]为走上第 i-2 级阶梯的走法，所以走上第i级阶梯的走法等于走上第i-1级阶梯的走法与走上第i-2级阶梯的走法之和，即dp[i]=dp[i-1]+dp[i-2]。

3.代码实现（Java）

//（1）动态规划
public int climbStairs(int n){
	//dp[i]为走上第i级台阶的走法
    int[] dp = new int[n+1];
    if(n<=1){
        return 1;
    }else if(n==2){
        return 2;
    }else{
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
/*
	思路1的代码优化（来自本题官方题解）
	上面代码中的dp(x)只和dp(x-1)与dp(x-2)有关，所以可以用滚动数组思想把空间复杂度优化成O(1)
*/
public int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i=1;i<=n;i++) {
        p=q; 
        q=r; 
        r=p+q;
    }
    return r;
}
//另外一种写法
public int climbStairs(int n) {
    int[] dp = new int[4];
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=n;i++){
        dp[i%4]=dp[(i-1)%4]+dp[(i-2)%4];
    }
    return dp[n%4];
}