题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 45

解答：

如图所示：

走第一步需要思考一个问题是一次走两个楼梯,还是一次走一个楼梯，之后的每一步都是这样思考，所以说这是一个典型的递归问题。

遇到递归先考虑终止条件；本题的终止条件就在走后一步的走法，是以一个楼梯结尾还是一两个楼梯结尾；

说以答案非常简单只有三行代码

public int climbStairs(int n){
      if (n==1) return 1;
      if (n==2) return 2;
    return=climbStairs(n-1)+climbStairs(n-2);
}

但是这个方法的实现的时间复杂度比较大，因为在递归的时候重复计算非常多，比如：要求f(5)必须要知道f(4)+f(3)，而要求f(4)就必须知道f(3)+f(2)，在这里f(3)就求了两次。所以我们要对代码进行优化。

我们可以创建一个HsahMap每求出一个值就把它保存到这个HsahMap中这样在下次用的时候就可以避免重复计算。

代码如下：

public class Solution {

private Map<Integer,Integer> storeMap = new HashMap<>();
public int climbStairs(int n){
    if (n==1) return 1;
    if (n==2) return 2;
    if (null!=storeMap.get(n))
        return storeMap.get(n);
    else {
        int result =climbStairs(n-1)+climbStairs(n-2);
        storeMap.put(n,result);
        return result;
    }
  }
}

时间复杂度为O(n)

除了递归的方法我们还可以用循环的方法来解决，既然从上往下会造成重复计算那么我们就从下往上来循环。这样也可以规避重复计算的问题。

代码如下：

public class Solution {//循环的解法，自底向上累加
       public int climbStairs(int n){
           if(n==1)return 1;
           if(n==2)return 2;
           int result=0;
           int pre = 2;
           int prPre =1;
           for(int i=3 ;i<=n;++i){
               result =pre +prPre;
               prPre=pre;
               pre=result;
           }
           return result;
       }
}

2023/9/17