[JAVA] LeetCode 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?

 

너는 계단을 오르고 있다. 정상에 오르려면 n개의 계단을 올라야 한다.

매 타임마다 너는 1개 또는 2개의 계단만을 오를 수 있다.

정상에 오를 수 있는 방법의 가짓수를 구하라.

 

 

풀이 방법

n의 값에 따른 방법의 가짓수를 정리해보면 아래와 같다.

n = 1일 때 1,

n = 2일 때 2,

n = 3일 때 3,

n = 4일 때 5 ...

 

위와 같이 증가하는 방법의 가짓수를 미루어보아

n = (n-1) + (n-2) 라는 공식을 얻을 수있다.

 

이를 구현만 하면 끝 !

 

class Solution {
    int[] arr = new int[46];
    
    public int climbStairs(int n) {
        arr[1] = 1;
        arr[2] = 2;
        for(int i=3; i<arr.length; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n];
    }
}