手撕一道算法题在你面前有一个n阶的楼梯，你一步只能上1阶或2阶。请问，当N=11时，你可以采用多少种不同的方式爬完这个楼梯（）；当N=9时呢？

比眉伴天荒 2022-11-24 15:28 104阅读 0赞

# **前言** #

今天偶然看到群里有小伙伴在讨论这道算法题，说实话算法题写的确实有些少了近期，都在忙着搬砖，所以简单做个记录。

# **题：** #

在你面前有一个n阶的楼梯，你一步只能上1阶或2阶。请问，当N=11时，你可以采用多少种不同的方式爬完这个楼梯（）；当N=9时呢？

## **核心思路，拆解：** ##

到达台阶 11时，有可能是通过走 1阶上来的 ；也可能是走2阶上来的；

所以统计出到达 台阶11，也就是统计出 到达10阶  + 到达9阶 的 方法总数。

那么到达10阶，同样 有可能是通过走 1阶上来的 ；也可能是走2阶上来的；

所以统计出到达 台阶10，也就是统计出 到达 9 阶  + 到达 8 阶 的 方法总数。

那么到达9阶，同样 有可能是通过走 1阶上来的 ；也可能是走2阶上来的；

所以统计出到达 台阶9，也就是统计出 到达 8 阶  + 到达 7 阶 的 方法总数。

一样以此类推......

那么到达3阶，同样 有可能是通过走 1阶上来的 ；也可能是走2阶上来的；

所以统计出到达 台阶3，也就是统计出 到达2 阶  + 到达 1 阶 的 方法总数。

而到达2阶，方法总数有两种， 分两次 1 台阶走 或者 一次走 2  台阶；

而到达1阶，方法总数有一种， 一次走 1 台阶；

## **代码解：** ##

public class Test {
    
        public static void main(String[] args) {
    
            //解法1
            Integer result1 = getMethodLoop(11);
            System.out.println(result1); //144
    
            //解法2
            Integer result2=getSumMethods(11);
            System.out.println(result2); //144
        }
        public  static int getMethodLoop(int sum){
    
            if (sum==1 ){
    
                return 1;
    
            }else if (sum==2){
    
                return 2;
    
            }else {
    
                int m1=sum-1;
                int m2=sum-2;
                int result=  getMethodLoop(m1)+getMethodLoop(m2);
                return  result;
            }
    
    
    
    
        }
    
    
        private static Integer getSumMethods(int sum) {
    
    
            Map<String,Integer> map=new HashMap<>();
            map.put("1",1);
            map.put("2",2);
    
            for (int i=3;i<=sum;i++){
    
                Integer m1=i-1;
                Integer m2=i-2;
                Integer m1Value = map.get(String.valueOf(m1)) ;
                Integer m2Value = map.get(String.valueOf(m2))  ;
                map.put(String.valueOf(i),m1Value+m2Value);
            }
            System.out.println(map.toString());
           return  map.get(String.valueOf(sum));
            //{11=144, 1=1, 2=2, 3=3, 4=5, 5=8, 6=13, 7=21, 8=34, 9=55, 10=89}
        }
    
    
    
    
    
    }