Climbing Stairs

🔗 문제 링크

https://leetcode.com/problems/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$

🗝 풀이 (언어 : Java)

기본적인 DP문제이다. 3부터 해당 순서의 계단은 전 계단과 전전 계단에 도착하는 경우의 수들의 합이다.

class Solution {
    public int climbStairs(int n) {
        // dp 배열
        int[] dp = new int[n+1];
        // 초기 2번째 까지 경우의 수 넣기
        dp[1] = 1;
        if (n >= 2)
            dp[2] = 2;
        // 해당 계단의 경우의 수는 전 계단의 경우의 수(1) + 전전 계단의 경우의 수(2)
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
}