【LeetCode】Climbing Stairs解題レポート

Climbing Stairs
[LeetCode]
https://leetcode.com/problems/climbing-stairs/
Total Accepted: 106510 Total Submissions: 290041 Difficulty: Easy
Question
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?
Ways
注意問題の意味は、いくつかの方法があります.つまり、3つの階段を加えると、1,2と2,1は違います.
方法1
フェブラッキーで列を数える方法.
どうしてですか.階段が1つ増えるたびに前の解法で任意のステップが1つ増えると考えられるからだ.ええ、私も分かりません.
前の数値を書けばわかります.

1 --> 1
2 --> 2
3 --> 3
4 --> 5
……

解法:

public class Solution {

    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

でも!タイムアウト!この方法は遅すぎるので、サイクル数が多すぎます.まさか!
方法2
LeetCodeが推奨するダイナミックプランニング.
参照先:http://blog.csdn.net/kenden23/article/details/17377869
ダイナミックプランニングでは、配列を作成し、最初から巡回する必要があります.この問題の各位置の結果は、最初の2つの数を加算します.最後の数値を見ればいいです.
フィポラチ数列に似ているのではないでしょうか.
この方法はアルゴリズムの効率が高いとは思わなかった.

public class Solution {

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

AC:0ms
達人はさすがに達人ですね.スペースの節約も考えました.
この方法は牛しか言えない!3つの空間でタスクを完了できます.リサイクルすればいいです.

public class Solution {

    public int climbStairs(int n) {
        int[] counts=new int[3];
        counts[0]=1;
        counts[1]=1;
        for(int i=2;i<=n;i++){
            counts[i%3]=counts[(i-1)%3]+counts[(i-2)%3];
        }
        return counts[n%3];
    }
}

AC:0ms
Date
2016/5/1 16:19:44