[Java] LeetCode 70. Climbing Stairs

문제

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

제한사항

1 <= n <= 45

 

입출력 예시

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

---

 

설명

지난번 풀었던 백준 계단 오르기 문제와 비슷하다.

 

이번 문제에서는 n개의 계단을 오를 때 오를 수 있는 방식 개수를 출력하면 되는 문제이다.

계단은 1칸 or 2칸 오르는 것이 가능하다.

 

n = 1 -> 1칸

n = 2 -> (1칸 + 1칸) + (2칸)

n = 3 -> (1칸 + 1칸 + 1칸) + (2칸 + 1칸) + (1칸 + 2칸)

 

여기까지 봤을 때 1칸과 2칸은 선택의 여지가 없지만 3칸부터는 선택을 할 수 있다.

n이 3일 때 2칸이 남아 있다면 현재 1칸을 올라온 것이고, 1칸이 남아있다면 현재 2칸을 올라온 것이 된다.

 

그러므로 1칸일 때 올라 갈 수 있는 방법 + 2칸일 때 올라갈 수 있는 방법, 즉 [i - 1] + [i - 2] 를 해주면 된다는 의미.

 

코드

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        if (n <= 2) return n;	// n이 2보다 작다면 n과 결과값이 같으므로 n 리턴
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++){	// 3부터 반복
            dp[i] = dp[i -1] + dp[i - 2];
        } 
        return dp[dp.length -1];	// 마지막값 출력
    }
}