[LeetCode/70/Java]Climbing Stairs

[LeetCode/70/Java]Climbing Stairs

풀이

class Solution {
    public static int[] buf = new int[46];    
    public int climbStairs(int n) {
        if (n <= 2) return n;
        if (buf[n] != 0) return buf[n];
        return buf[n] = climbStairs(n - 1) + climbStairs(n - 2);
    }
}

후기

아래와 같은 패턴을 가지고 있습니다.

n = 2 1. 1 + 1 2. 2 n = 3 1. (1 + 1) + 1 2. 1 + (2) 3. 2 + 1 n = 4 1. (1 + 1 + 1) + 1 2. (1 + 2) + 1 3. 1 + 1 + 2 4. (2 + 1) + 1 5. 2 + 2 n = 5 1. (1 + 1 + 1 + 1) + 1 2. (1 + 2 + 1) + 1 3. (1 + 1 + 2) + 1 4. 1 + 1 + 1 + 2 5. (2 + 1 + 1) + 1 6. 1 + (2 + 2) 7. 2 + 1 + 2 8. 2 + 2 + 1

자세히 보면 피보나치 수열의 응용인데 차이점이라면 n = 2일때 피보나치 수열은 0 + 1이라서 1이지만 해당 알고리즘은 2일 경우에도 2가지의 경우의 수가 있기 때문에 2입니다.

time complexity O(N)
space complexity O(1)