关于爬楼梯问题以及优化

aries-cy 2018-02-22 原文

题目是这样的：

假设你正在爬楼梯，一共有N阶楼梯。但每次你只能爬一阶或者两阶，你能有多少种不同的方法爬到楼顶部？

初出茅庐，面试被问到，回家做个笔记记录一下。

最先想到的应该是用递归的方法解：

public static int climbStairs1(int n) {
        int ways;
        if(n==1||n==2) {
            ways = n;
        }else {
            ways = climbStairs1(n-1)+climbStairs1(n-2);
        }
        return ways;
    }

这样解表面固然没毛病，但是学习算法的时候应该听过递归的方法慎用，慎用，慎用！重要的事情说3遍…这个方法当N很大时，时间复杂度成指数型的增长，问题很大啊~

于是乎，面试官问道，你有什么优化的方法嘛？（我有好的方法，不就直接写出来了嘛？不过感觉面试官都喜欢由浅入深，(￣▽￣)”）

上网查询了一下，确实有一些不一样的方法：

public static int climbStairs2(int n) {
        if(n==0)
            return 1;
        int[] arr = new int[n+1];
        arr[0]=1;
        arr[1]=1;
        for(int i=2;i<=n;i++) {
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr[n];
    }

这个方法是利用动态规划来解决问题的，利用数组来存储有多少种方法（与第一种那个方法比，实际就是利用空间换取时间，即空间复杂度很大），当N很大的时候，仍会出现问题，不过对于面试来说的话应该足够了…

网上有种斐波那契数列的通项公式，有大神还能想得起来，做得出来，也是很强

public static int climbStairs4(int n) {
         if (n == 0)
                return 1;
            if (n == 1 || n == 2)
                return n;
            int result = (int) Math.floor(
                    1 / Math.sqrt(5) * (Math.pow((1 + Math.sqrt(5)) / 2, n + 1) - Math.pow((1 - Math.sqrt(5)) / 2, n + 1)));
            return result;
    }

这个方法确实解决了时间复杂度和空间复杂度的问题，当N很大时，不会出现问题，有兴趣的可以去研究研究斐波那契数列…