70. Climbing Stairs / LeetCode

Dynamic Programming을 recurssion으로 사용해서 아래와 같이 풀면, 시간 초과로 failed 이 됩니다.
시간 초과에 대한 자세한 내용은 아래 블로그에 잘 설명되어 있습니다.
https://sedew.tistory.com/m/44

입력값 N 의 N+1만큼 메모리를 사용해서, sub problems의 결과를 메모리에 저장해서, 한번 계사한 sub problem은 다시 계산하지 않도록 코딩해보겠습니다.

class Solution {
    public int climbStairs(int N) {
        if(N < 2) {
            return N;
        }

        int r[] = new int[N+1];
        r[0] = 1;
        r[1] = 1;

        for(int i=2; i<=N; ++i)
            r[i] = r[i-1] + r[i-2];

        return r[N];
    }
}