[Leetcode][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?

 

계단을 올라보자. input으로 n을 받고 해당 값은 맨 위로 가기 위한 스텝의 개수이다.

각각 1 또는 2개의 계단만 오를 수 있다. 몇가지 방법으로 맨 위로 올라갈 수 있는지 구해라

---

해당 문제에서 n까지 도달하기 위한 방법은, 유저가 올라 갈 수 있는 계단의 개수는 1 또는 2 이므로,

f(n) = f(n-1) + fn-2) 로 표현될 수 있다.

이러한 형태의 문제는 dynamic programming을 통해서 해결될 수 있다.

추가적으로, 방문 했던 위치는 해당 위치로 올 수 있는 개수를 따로 저장해 두고 또 방문했을 때 재 계산을 하지 않고 저장된 값을 불러서 사용하면 된다. 

먼저, 위의 식 처럼 해결할 수 있는 Top-Down 방식을 보자. 

    private int df(int n, int[] t) {
        if (n == 1) {
            return 1;
        }
        if (n == 0) {
            return 1;
        }
        if (t[n] != 0) {
            return t[n];
        }
        int n1 = df(n - 1, t);
        int n2 = df(n - 2, t);
        t[n] = n2 + n1;
        return n1 + n2;
    }

그럼 해당 코드를 호출하는 부분을 보자

    public int climbStairs(int n) {
        int[] t = new int[n + 1];
        t[0] = 1;
        t[1] = 1;
        int rst = df(n, t);
        return rst;
    }

 

그럼, 다음으로 Bottom-Up 방식을 보자

    public int climbStairs(int n) {
        int[] t = new int[n];
        t[0] = 1;
        t[1] = 1;
        for (int i=2; i<n; i++) {
        t[i] = t[i-1] + t[i-2];
        }
        return t[n-1];
    }

문제 출처 :

leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode