[다이나믹 프로그래밍 (DP)] LC #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?

Example 1:

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

Example 2:

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

Constraints:


문제 링크: https://leetcode.com/problems/climbing-stairs/

1. 문제의 핵심: 동적 프로그래밍과 피보나치 수열

이 문제는 동적 프로그래밍(DP)의 가장 대표적인 입문 문제입니다. 큰 문제를 작은 문제로 나누어 해결하는 DP의 핵심 사상을 이해하기 좋습니다.

핵심 아이디어: n번째 계단에 도달하는 방법의 수는, (n-1)번째 계단에 도달하는 방법의 수와 (n-2)번째 계단에 도달하는 방법의 수의 합과 같다.

왜냐하면 n번째 계단에 오르기 위한 마지막 스텝은 반드시 (n-1)번째 계단에서 한 칸을 오르거나, (n-2)번째 계단에서 두 칸을 오르는 두 가지 경우밖에 없기 때문입니다. 이는 피보나치 수열의 점화식 F(n) = F(n-1) + F(n-2)와 정확히 일치합니다.

2. 해결 전략

  1. 기저 사례(Base Case)를 정의합니다. n=1일 때는 1가지, n=2일 때는 2가지 방법이 있습니다.
  2. 단순 재귀로 풀면 동일한 계산을 반복하여 시간 초과가 발생하므로, 계산 결과를 저장하며 풀어가는 동적 프로그래밍(Bottom-up) 방식을 사용합니다.
  3. 전체 배열(DP 테이블)을 만들 필요 없이, 단 두 개의 변수만 사용하여 이전 값과 그 이전 값을 저장하며 공간을 최적화합니다.
  4. 3부터 n까지 반복하면서 점화식 current = one_step_before + two_steps_before를 적용하여 값을 갱신해 나갑니다.

3. Java 코드 구현

class Solution {
    public int climbStairs(int n) {
        // 기저 사례 처리
        if (n <= 2) {
            return n;
        }

        // DP를 위한 변수 (공간 최적화)
        int two_steps_before = 1; // n=1일 때의 방법 수
        int one_step_before = 2;  // n=2일 때의 방법 수

        // 3부터 n까지 반복하며 점화식 적용
        for (int i = 3; i <= n; i++) {
            int current_ways = one_step_before + two_steps_before;
            two_steps_before = one_step_before;
            one_step_before = current_ways;
        }

        return one_step_before;
    }
}

💡 코드 세부 포인트