70. 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?

链接： http://leetcode.com/problems/climbing-stairs/

题解：

费波纳茨序列，使用Dynamic Programming，先构建一个一维数组。Time Complexity - O(n)， Space Complexity - O(n)。

public class Solution {
    public int climbStairs(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;

        for(int i = 2; i < n + 1; i ++){
            result[i] = result[i - 1] + result[i - 2];
        }

        return result[n];
    }
}

可以继续优化空间复杂度，使用两个变量存储之前的值。 Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {
    public int climbStairs(int n) {
        int result = 1, prevStep = 1, curStep = 1;
        
        for(int i = 2; i < n + 1; i ++){
            result = prevStep + curStep;
            prevStep = curStep;
            curStep = result;
        }
        
        return result;
    }
}

Update: 前几天BB的电面遇到这一题，不过是三个数，所以要用 first + second + third

public class Solution {
    public int climbStairs(int n) {
        if(n < 2)
            return 1;
        int first = 1, second = 1, res = 0;
        
        for(int i = 2; i < n + 1; i++) {
            res = first + second;
            first = second;
            second = res;
        }
        
        return res;
    }
}

还可以继续优化 - 使用矩阵法计算Fib。 Time Complexity - O(logn)，Space Complexity - O(1).

http://www.gocalf.com/blog/calc-fibonacci.html

二刷：

矩阵法确实比较快，在Dasgupta的Algorithms那本书里见到过，但还从来没试过怎么写。所以还是用了dp。关于dp仍然要好好学习和练习，搞清楚应该如何思考。

这里dp的时候，新建dp数组是new dp[n + 1]，为什么这里要加1呢? 我觉得主要就是节省边界条件的代码。也要看我们怎么定义，我们定义dp[i]是到第i步为止的总步数，那么dp[0]就是第0步为止，dp[1]就是第一步为止，dp[2] = dp[0] + dp[1]是第二步为止我们有多少方法。那么最后dp[n]就是到第n步为止，那么数组总长度其实是 n + 1。这个跟其他dp，比如Edit Distance差不多，都要考虑一下初始状态，比如Edit Distance我们就要对两个字符串都为空时进行初始化，然后才能在遍历过程中套用转移方程。

Java:

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n <= 2) {
            return n;
        }
        int climbOneStep = 2, climbTwoStep = 1;
        int curSteps = 0;
        
        for (int i = 3; i <= n; i++) {
            curSteps = climbOneStep + climbTwoStep;
            climbTwoStep = climbOneStep;
            climbOneStep = curSteps;
        }
        return curSteps;
    }
}

题外话：

2/4/2016

最近几天突然忙起来了。工作，健身，上课。看书学习以及做题的时间被很大程度压缩了。还是要好好搞一搞time management。很羡慕那些有精力又会管理时间的人。

三刷:

又回来考虑了为什么dp写不好，这是因为自己没有学好系统的方法。一般要分为几个步骤，

1. 定义dp含义

2. 初始化

3. 转移方程

还有，这些可以递归的题目，跟离散数学里的同质性方程和异质性方程的解都很有关系。没有学过离散数学，缺少系统级知识的支持，对我来说自然很难写好...多学多练吧。

1d dp

Java:

Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {
    public int climbStairs(int n) {
        if (n < 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

压缩空间复杂度:

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {
    public int climbStairs(int n) {
        if (n < 0) {
            return 0;
        }
        int curSteps = 1;
        int oneStepBack = 1;
        int twoStepsBack = 1;
        
        for (int i = 2; i <= n; i++) {
            curSteps = oneStepBack + twoStepsBack;
            twoStepsBack = oneStepBack;
            oneStepBack = curSteps;
        }
        return curSteps;
    }
}

矩阵法:

如何证明还不确定，但主要是利用一个公式。 f(0) = 1, f(1) = 1，这样我们就可以快速求出在 n >= 1情况下， f(n + 1)的值。

[f(n - 1)  f(n)     ]    =  [ 0   1 ]ⁿ
[f(n)      f(n + 1) ]       [ 1   1 ]

Time Complexity - O(logn)， Space Complexity - O(1) - 留给下次解。

http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

Reference:

https://leetcode.com/discuss/16866/basically-its-a-fibonacci

https://leetcode.com/discuss/71958/using-the-fibonacci-formular-to-get-the-answer-directly

https://leetcode.com/discuss/42044/3-4-short-lines-in-every-language

https://www.zhihu.com/question/23995189 - 动态规划

http://www.hawstein.com/posts/dp-novice-to-advanced.html

http://kukuruku.co/hub/algorithms/the-nth-fibonacci-number-in-olog-n