[LeetCode] - Climbing Stairs

Memoization문제

 

sudo code

n개의 계단을 올라간다
한걸음에 1 또는 2개 계단을 올라갈 수 있다
1 <= n <= 45
1 - [1]
2 - [1,1] [2]
3 - [1,1,1] [1,2] [2,1]
4 - [1,1,1,1] [1,1,2] [1,2,1] [2,1,1] [2,2]
5 - [1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1] [1,2,2] [2,1,2] [2,2,1]

결과의 가짓수가 n-2 + n-1 fibo랑 같다
메모이제이션 활용하여 더해주기 O(N)이 될 것이다.

 

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