問題
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...
自分の解答2
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する。自分の1つ目と一緒。ただちょっと考え方が違ったので面白い。 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を2次元配列にする、くらいか?ただしてもメモリは少しスリムになる気はするが、 != 0の判定が入ってコードはちょっと汚くなりそう。まあこのままで良いかなぁ。
今後のための考え方
- 提出前に計算量を求めて爆発しそうであればなにか工夫してからSubmitする
- 時間超過したら無駄な計算はしないように結果をMapに保持しよう