(DP, Easy) Climbing Stairs

https://leetcode.com/problems/climbing-stairs/description/

DP의 입문이고 많이 본 문제다. 간단하게 풀어본다.

1까지 가는 경우의 수 = 1 (1 step)
2까지 가는 경우의 수 = 2 (1 step + 1 step OR 2 steps)

3부터는 i-1 + i-2가 됨
왜냐? 1 step으로 가는 경우의 수 + 2 step으로 가는 경우의 수기 때문

샘플로 보자. 괄호는 i-1, i-2에서 온 경우를 의미한다.
이후 1 step 또는 2 steps 점프가 가능하다.

3은

• (1 + 1) + 1
• (1) + 2
• (2) + 1

4를 보면

• (1 + 1 + 1) + 1
• (1 + 1) + 2
• (1 + 2) + 1
• (2) + 2
• (2 + 1) + 1

결국 i-1, i-2로부터 스탭을 붙일 가능성이 생겨나는 것이기 때문에 아래와 같이 풀 수 있다.

시간복잡도는 O(n)이다.

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        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];
    }
}