LeetCode 70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

 

Dynamic Programming 활용 문제

난이도 : easy

 

* IT's LIT 2주차

class Solution {

    /* Runtime: 0 ms, memory: 39.5 MB */
    public int climbStairs(int n) {
        int[] stair = new int[n+1];
        stair[0] = 1;
        stair[1] = 1;

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

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

}

 

Dynamic Programing이 어떤건지 몰라서

마침 이번학기에 재수강(ㅠ)하는 방통대 알고리즘 과목에서

해당 강의 개념부분을 보면서 피보나치 수열을 예시로 배웠는데
그러고나서 이 문제를 보니 거의 유사한 문제 같아서 적용함

사실 강의 보고 배운대로 풀긴 풀었는데 자세한 원리는 제대로 이해 못해서
문제 풀어놓고 neetcode 영상 보고 다시 이해함

 

 

다른 사람들 솔루션 봤을때 나와 다른점 :
0계단 올라가는 방법을 0이라고 하고 1계단, 2계단까지 구해놓고 돌리던데
나는 안올라가는 것도 방법이라 1이라고 생각해서 0계단, 1계단까지만 구하고 돌림...

그런데 constraints에 1 <= n <= 45 이라고 되어있었다....

여하튼 계산하는데 영향은 없는듯 정답처리됨

 

 

 

* 참고

방통대 알고리즘 5강 (동적 프로그래밍 개념, 피보나치 수열)

NeetCode 영상 https://youtu.be/Y0lT9Fck7qI