Climbing Stairs: DP

First Thoughts: problem itself inherently recursive (adding bits to previous answer) -> much like Fibonacci number solution, where answer is the sum of partial answers

My Solution:

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

Catch Point:

1. 사실 이번 문제는 답을 구하는 로직이 더 중요했던 것 같다. 피보나치 수열과 같은 메커니즘으로 작동한다는 것을 캐치하는 것이 중요했던 것 같다.

2. 처음에는 정말 쌩 recursion으로 풀었는데, time limit exceeded 떴다. 왜 그런지는 아직 알아내지 못했다..