[LeetCode] 70. Climbing Stairs

leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

재귀함수 연습하기!

• 계단을 오를 수 있는 경우의 수 return
• 한번에 1개 혹은 2개의 계단을 오를 수 있다.
• 1 <= n <= 45

public class Solution {
    public int climbStairs(int n) {
        return climb_Stairs(0, n);
    }
    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
}

 

기본적으로 이번 문제는 피보나치 수열과 풀이가 같다. 

• n 이 1일 때, 1 개의 방법이 있다.  
• n 이 2일 때, 2 개의 방법이 있다. (1계단씩 두번 오르는것과, 2계단씩 한번 오르는 것)
• n 이 3일 때, 다시 1개의 계단을 먼저 오르는지, 2계의 계단을 먼저 오르는지로 나뉘므로 n이 3일 때는 n이 1일때와 2일때를 더하면 된다.

 

DP 로 푸는 방법

public class Solution {
	public int climbStairs_arr(int n) {
        if(n <=2){
            return n;
        }

        int [] answer = new int[n];
        answer[0] = 1;
        answer[1] = 2;

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

        return answer[n-1];
    }
}

 

 

 

참고 : [LeetCode] 509. Fibonacci Number (JAVA)