[Leetcode] Climbing Stairs (DP) - java

Climbing Stairs - LeetCode

문제 파악

계단을 오를 수 있는 칸수는 1과 2이다.

이를 이용해서 자연수 n (1~45)칸을 오르기 위한 방법 수를 구하는 문제

 

1칸을 오르기 위해서는 1로 1가지, 2칸을 오르기 위해서는 1+1, 2로 2가지이다.

3칸을 오르려면 1+1+1, 2+1 인데 2칸을 오르는 경우가 2가지이므로 총 3가지이다.

---

접근 방법

우선 1칸과 2칸을 오르는 경우가 주어져있기 때문에 기본값으로 추가한다.

그리고 3의 경우를 보면 1칸을 오르는 방법 + 2칸을 오르는 방법의 수를 더한 값이다.

이를 명확하게 확인하기 위해서 4칸을 보면 2칸을 오르는 3+1 , 2+2 로 구할 수 있다.

3칸을 오르는 경우 3가지 + 2칸을 오르는 경우 2가지를 더하면 총 5가지가 된다.

 

즉, n칸을 오르기 위해서는 n-1칸을 오르는 방법의 수 + n-2칸을 오르는 방법의 수가 된다.

 

$$F(n) = F(n-1) + F(n-2), F(1) = 1, F(2) = 2$$

---

코드 구현

class Solution {
    public int climbStairs(int n) {
        // 초기화
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(1,1);
        dp.put(2,2);

        // 점화식
        for(int i = 3; i <= n; i++){
            dp.put(i, dp.get(i-1) + dp.get(i-2));
        }

        return dp.get(n);
    }
}