[LeetCode] 70. Climbing Stairs

70. Climbing Stairs

LeetCode

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?

당신은 계단을 오르고 있습니다. 꼭대기에 도달하려면 n개의 계단을 올라야 합니다.
한 번에 1계단 또는 2계단씩 오를 수 있습니다. 꼭대기까지 오르는 서로 다른 방법은 총 몇 가지입니까?

 

Example

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

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

---

1. 문제 요구사항 분석

n개의 계단을 오르는 서로 다른 방법 구하기 → Dynamic Programming

 

2. 접근 전략

떠오르는 생각: 수학적으로 풀 수 있지 않을까?

1개의 계단: 1개 → 1가지

2개의 계단: 2개 / 1개 + 1개 → 2가지

3개의 계단: 1개 + 2개 / 2개 + 1개 / 1개 + 1개 + 1개 → 3가지

4개의 계단: 2개 + 2개 / 1개 + 1개 + 2개 / 1개 + 2개 + 1개 / 2개 + 1개 + 1개 / 1개 + 1개 + 1개 + 1개 → 5가지

1 → 2 → 3 → 5 가지 => 수열 ?!

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

 

😭  피보나치 수열 그대로 코드로 구현: 시간초과 O(2^n)

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

 

😄 메모이제이션 사용 (탑다운 동적계획법): 시간복잡도 O(n)

class Solution {
    Integer[] memo; // 밑에서 != null을 하기 때문에 객체로 선언
    
    public int climbStairs(int n) {
        memo = new Integer[n + 1];
        return climb(n);
    }

    public int climb(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        memo[1] = 1;
        memo[2] = 2;

        if (memo[n] != null) {
            return memo[n];
        }

        memo[n] = climb(n - 1) + climb(n - 2);
        return memo[n];
    }
}

 

😄 배열 사용하지 않고 하는 방법(바텀업 동적 계획법): 시간복잡도 O(n)

class Solution {
    public int climbStairs(int n) {
        if(n == 1 || n == 2){
            return n;
        }
        
        int a = 1;
        int b = 2;
        for(int i = 3;i <= n;i++){
            int ways = a + b;
            a = b;
            b = ways;
        }
        
        return b;
    }
}