[LeetCode] 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, 2 계단을 오를 수 있는데 몇 가지 경우의 수가 있어?

첫 생각

당근 DFS로 돌려야지 ~

class Solution {
    public int climbStairs(int n) {
        return dfs(n);
    }

    private int dfs(int n) {
        // 기저 사례 처리
        if (n == 0) {
            return 1; // 올바른 경로 찾음
        }
        if (n < 0) {
            return 0; // 경로가 무효
        }

        // 각 단계에서 가능한 경우의 수 누적
        int count = 0;
        for (int i = 1; i <= 2; i++) {
            count += dfs(n - i);
        }

        return count;
    }
}

아... 시간초과..

DP !!

class Solution {
	// 조건이 1 <= n <= 45
    static int[] dp = new int[46];

    public int climbStairs(int n) {
        if(n <= 2) return n;

        if(dp[n] != 0) return dp[n];
        dp[n] = climbStairs(n - 1) + climbStairs(n - 2);
        return dp[n];
    }
}

바로 통과...! 이래서 DP가 중요한겁니다.. 근데 그걸 이제 깨달은..