[java] Climbing Stairs

[참고문제] :https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

문제 풀이

DP문제다.

DP는 일단 규칙찾기, 점화식 찾기다. 못찾으면 끝나는 문제라고 할 수 있다.

 

생각의 흐름 - 초기값들을 찾자.

문제에서 보이듯, n = 1, n = 2, n = 3일 때를 보여주고 있다.

점화식 문제처럼 초기값들을 먼저 설정해보자.

 

생각의 흐름 - 일단 적어보자.

바로 안보이면, 난 일단 적어본다. 생각날 때까지 적다보면, 규칙이 보인다.

 

이번에도 n=6정도까지 적어보니, 금방 규칙이 보였다.

public int climbStairs(int n) {
    int[] arr = new int[45];

    arr[1] = 1;
    arr[2] = 2;
    if(n == 1) {
        return 1;
    }

    else if(n == 2) {
        return 2;
    }

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

   return arr[n];
}