2018-05-15 70. Climbing Stairs

题意：爬楼梯，一次可以爬1阶或2阶，输入正数n，输出爬到n阶楼梯总共有几种策略。
解题思路：
方法一：动态规划DP，一次可以上1阶或2阶，那么到第n阶可以从第n-1阶上1阶，或者从n-2阶上2阶，所以到第n阶的策略等于到第n-1阶加到第n-2阶的策略总和。到第1阶1种方法，到第2阶2种方法，到第3阶有1+2=3种方法，到第4阶有2+3=5种方法... 其实就是斐波那契数列。
时间复杂度：O(n)，遍历到n。
空间复杂度：O(1)，仅使用固定内存。

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

方法二：使用矩阵计算斐波那契数列F(n)
时间复杂度：O(log(n))。
空间复杂度：O（1）。