Leetcode70. 爬楼梯

题目传送地址： https://leetcode.cn/problems/climbing-stairs/

运行效率：

代码如下：

   public static int climbStairs(int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int i = climbStairsWithMap(n, map);
        return i;
    }
//用map可以提升查询性能，加快查询速度
    public static int climbStairsWithMap(int n, HashMap<Integer,Integer> map){
        if(map.containsKey(n)){
            return map.get(n);
        }
        //处理边界条件
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        //要爬到第n阶，可以有2种办法，第一种是从n-1阶跳一格到n阶     第二种是从n-2阶跳2格到n阶
        int i = climbStairsWithMap(n - 1, map) + climbStairsWithMap(n - 2, map);
        map.put(n,i);
        return i;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22