70.Climbing Stirs

タイトル:
You are climbing a stair case.It taes n steps to reach to the top.
Each time you can einther climb 1 or 2 steps.In how many distinct ways can you climb to the top？
リンク:  http://leetcode.com/problems/climbing-stairs/
クイズ:
フィボナッツシーケンスは、Dynamic Prograammingを用いて、まず1次元配列を構築する。Time Coplexity-O（n），Space Coplexity-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];

    }

}

 
空間複雑さを引き続き最適化し、2つの変数を使用して保存する前の値を使用することができます。Time Coplexity-O(n)、Space Coplexity-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;

    }

}

 
また、最適化を継続することができます。マトリックス法を用いてFibを計算します。Time Complexity-O（logn），Space Coplexity-O（1）.
http://www.gocalf.com/blog/calc-fibonacci.html 
テスト：