LeetCode(70题)--爬楼梯[JAVA]_爬楼梯算法详解 java

---

一、题目描述与分析

 不难看出，这是一道常见的递归算法题型。

f(n)={

         1  n=1；

          2 n=2;

          f(n-1)+f(n-2) n>2;

}

二、解题代码及算法描述

推出公式后，首先想到的是普通递归思路解题。

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

提交结果： 

但这样会超出时间限制，时间复杂度太高Of(n*n),这里我们以n==5为例说明原因

由图可看出，在递归的过程中求f(3),f(2),f(1)时会重复的进行求解，所以时间复杂度会非常高。导致超时。

解决方法1：

我们可以把已经求过的值放到hashmap中，这样用的时候找有没有对应n的值，如果有就直接用，没有就进行计算后保存到hashmap中。算法时间复杂度为O（n）。

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(storeMap.get(n)!=null){
            return storeMap.get(n);
        }else{
            int result=climbStairs(n-1)+climbStairs(n-2);
            //把结果存入HashMap中
            storeMap.put(n,result);
            return result;
        }
    }
}

提交结果：

 超越100%用户。

 

 解决方法2：

我们可以用循环解决问题。正向思维想算法。f1表示f(n-1)，f2表示f(n-2)的值，从3开始。f(3)=f1+f2；到f(4)时，f1=f(3)的值，f2=f1的值。以此类推写算法。时间复杂度也是O(n).

class Solution {
  
    public int climbStairs(int n) {
 
        //通过,超过100%用户
         if(n==1) return 1;
         if(n==2) return 2;
         int f1=2,f2=1,sum=0;
         for(int i=3; i<=n;i++){
             sum=f1+f2;
             f2=f1;
             f1=sum;
        }
        return sum;
 
       
    }
}

 提交结果：

  超越100%用户。

---