LeetCode(DP)Climbing Stairs

2018-06-15

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

思路：爬楼梯，每次只能爬1阶或者2阶，总共有n阶，求共有多少种爬法，用f(n)来表示这个要求解的函数。首先需要分解这个问题：如果n为1时，只有1中爬法，就是1 step。如果n为2，可以一步上两个也可以分两步一次一个台阶，总共有2种方法。当楼梯为3阶及以上时可以这样看待这个问题，如果有n个台阶，那么我先上一个台阶就剩下了n-1个台阶，而求n-1个台阶有多少种爬法就是f(n-1)的值，而如果我先上了两个台阶，剩下的台阶就是f(n-2)。而每次只能上一个或者两个，故f(n)=f(n-1)+f(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);
    }
}

　　分析超时的原因，就是我们做了很多次重复的计算，比如计算n=4的时候，我们会算f(4)=f(3)+f(2)，而因为要计算f(3)，所以我们还要计算f(3)=f(2)+f(1)。这样在计算n=5的时候，我们又要计算f(4)中所有的计算量，以及还要再做一次f(3)。这样就重复计算了很多次之前已经计算过得结果，尤其是当数据量很大的时候，这样的递归时间复杂度和空间复杂度都很大。所以，我们要想办法减少计算量，最好能在每次计算f(3)和f(4)结束后可以保存他们计算的结果，这样当计算f(5)的时候只需要将这两个结果加起来就好了，会大大减少计算量。要保存这n个结果，每n层楼梯都对应着各自的f(n)，容易想到利用数组，优化后的代码如下：这其实就是动态规划的方法

//这就是动态规划的方法：DP
class Solution {
    public int climbStairs(int n) {
        //为了防止数组越界
        if(n==1){
            return 1;
        }
        if(n==0){
            return 0;
        }
        int [] arr=new int [n];
        arr[0]=1;
        arr[1]=2;
        for(int i=2;i<n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n-1];
    }
}

　　其实以上的方法还能优化，因为我们在考虑n的时候，只需要n-1的结果和n+1的结果，所以理论上我们要维护到最终的值只有两个f(n-1)和f(n-2)。其他之前的f(n)都可以覆盖掉，这样会优化我们算法的空间复杂度，代码如下：

//优化后的动态规划，时间O(n)，空间O(1)
class Solution {
    public int climbStairs(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int minustwo=1;
        int minusone=2;
        int result=0;
        for(int i=3;i<=n;i++){
            result=minusone+minustwo;
            minustwo=minusone;
            minusone=result;
        }
        return result;
    }
}