leetcode70.爬楼梯

我刚看到这道题，有点没有头绪，我想到了可能是动态规划，但是还是没有头绪

看了答案知道：

我们用 f(x)表示爬到第 x级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子： f(x)=f(x−1)+f(x−2)

有了这个规律就真简单了

可见对于算法题，一定要先分析题目，当成一个数学题去找思路，对于算法来说更多的是去找规律

我们找到了 以上的规律一下子简单起来了

可以递归：

public static int climbStairs(int n) {//递归法
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }

但是这在运行的时候是超时的，递归对性能的消耗确实比较大，因为每次递归都是对整个方法的压栈出栈等操作。

动态规划：

public static int climbStairs2(int n) {//动态规划
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int[] dp = new int[n+1];//这里申请了n+1个长度数组，但是代码发现我们只需要记录三个数字就好了，所以可以改进
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

用这种方法可以通过，但是很明显内存消耗比较大，我们每次都只用到三个值，只返回最后一个值

所以没有必要用一个数组来存放了，就用变量存储就可以了，这样就把O(N)的空间复杂度降低到了O(1)

public static int climbStairs3(int n) {//动态规划改进
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int first = 1;
        int second = 2;
        int third;
        for (int i = 3; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return second;
    }

通过运行明显发现内存的消耗变小了