[JAVA] 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:

• 1 <= n <= 45

아이디어

풀이

class Solution {
    public int climbStairs(int n) {
        //전체 범위
        int[] result = new int[46];

        result[0] = 0;
        result[1] = 1;
        result[2] = 2;

        for(int i = 3; i<=n; i++){
            result[i] = result[i-1] + result[i-2];
        }
        
        return result[n];
    }
}

다른 풀이

Recustion (Top Down Approach)

/**
 * Question   : Climbing Stairs
 * Complexity : Time: O(2^n) ; Space: O(n)
 */
class Solution {
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Recustion + Memorization (Top Down Approach)

/**
 * Question   : Climbing Stairs
 * Complexity : Time: O(n) ; Space: O(n)
 */
class Solution {
    public int climbStairs(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        memo.put(1, 1);
        memo.put(2, 2);
        return climbStairs(n, memo);
    }

    private int climbStairs(int n, Map<Integer, Integer> memo) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        memo.put(n, climbStairs(n - 1, memo) + climbStairs(n - 2, memo));
        return memo.get(n);
    }
}

- 각각의 재귀 로직 내에서 동일한 주소값을 갖고있는 Map에 데이터를 저장

- 시간복잡도 차이 확인 필요

DP (Bottom Up Approach)

/**
 * Question   : Climbing Stairs
 * Complexity : Time: O(n) ; Space: O(n)
 */
class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

- 내가 푼 방법

- 기본 배열을 동적으로 구성하였음, 0번배열의 값은 초기화해줄 필요 X

- 굳이 재귀를 사용할 필요가 있나 싶다...(재귀 너무 싫음)

DP + Optimization (Bottom Up Approach)

/**
 * Question   : Climbing Stairs
 * Complexity : Time: O(n) ; Space: O(1)
 */
class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }

        int prev1 = 1;
        int prev2 = 2;

        for (int i = 3; i <= n; i++) {
            int newValue = prev1 + prev2;
            prev1 = prev2;
            prev2 = newValue;
        }

        return prev2;
    }
}

- 새 값을 계산하기 위해 앞의 두 값만 활용하므로 굳이 배열에 저장할 필요가 없음..!