99클럽 코테 스터디 6일차 TIL + LeetCode 70 (Climbing Stairs, java)

오늘의 학습 키워드

• 피보나치 수열
• 다이나믹 프로그래밍 (DP)

문제 탐색하기

문제

문제 풀이 설계하기

예시를 들어서 설명하면 n을 5라고 했을 때 5가 될 수 있는 경우의 수는 연산에는 1또는 2만 사용할 수 있으므로

4가 될 수 있는 경우의 수에서 + 1을 하는 것과 3이 될 수 있는 경우의 수에서 +2를 하면 됩니다.

f(n) = f(n-2) + f(n-1)

 

따라서 위와 같은 식이 성립이 되는데 이를 풀기 위해서 반복문을 통해 각 수가 될 수 있는 경우의 수를 계속 구해주면 됩니다.

 

코드

class Solution {
    public int climbStairs(int n) {

        int[] nArr = new int[46];
        nArr[1] = 1;
        nArr[2] = 2;

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

        return nArr[n];
    }
}

 

오늘의 회고

다이나믹 프로그래밍을 통해 문제를 풀 수 있는 좋은 경험이었습니다.