LeetCode Study : 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?

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

https://leetcode.com/problems/climbing-stairs/

自分の解答

public int climbStairs(int m) {
    if (m <= 3) {
        return m;
    }
    return climbStairs(m - 1) + climbStairs(m - 2);
}

Time Limit Exceeded

初めてのTime Limit Exceeded...

自分の解答２

Map<Integer, Integer> stepMap = new HashMap<>();

public int climbStairs(int m) {
    if (m <= 3) {
        return m;
    }
    if (stepMap.containsKey(m)) {
        return stepMap.get(m);
    }
    int steps = climbStairs(m - 1) + climbStairs(m - 2);
    stepMap.put(m, steps);
    return steps;
}

再計算が大量に発生していたので、Mapに結果を保持するようにしたら時間超過しなくなった。

コード理解

別解 Brute Force

public int climbStairs(int n) {
    climb_Stairs(0, n);
}
public int climb_Stairs(int i, int n) {
    if (i > n) {
        return 0;
    }
    if (i == n) {
        return 1;
    }
    return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}

Time : / Space :

別解もTime Limit Exceededする。自分の１つ目と一緒。ただちょっと考え方が違ったので面白い。 nを固定しiを増やしてiがnを超えたらそれは存在しないので0と数える、という考え方。

また、フィボナッチ数列と気づけば以下のような答えも

別解

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

別解

public int climbStairs(int n) {
    if (n < 4) {
        return n;
    }
    double root5 = Math.sqrt(5);
    return (int) Math.round(Math.pow((1 + root5) / 2, n + 1) / root5);
}

最後の奴が最速最強。フィボナッチ数列の一般項。 qiita.com

自分の解答を良くするとしたら、HashMapを２次元配列にする、くらいか？ただしてもメモリは少しスリムになる気はするが、 != 0の判定が入ってコードはちょっと汚くなりそう。まあこのままで良いかなぁ。

今後のための考え方

• 提出前に計算量を求めて爆発しそうであればなにか工夫してからSubmitする
• 時間超過したら無駄な計算はしないように結果をMapに保持しよう