[LeetCode] 70. Climbing Stairs [JAVA(자바)]

문제 👉 <Climbing Stairs - LeetCode>

1. 문제 (계단 오르기)

계단을 매번 1개 혹은 2개를 오를 수 있을 때, 계단을 오르는 방법은 몇개인가?

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

2. 풀이

다이나믹 프로그래밍 (DP) 을 이용한 풀이

• 피보나치 수열 (단순 재귀 함수)
  • f(n) = f(n-1) + f(n-2)
  • f(5) = f(4) + f(3) -> 재귀함수를 통해 반복적인 연산 수행
  • f(4) = f(4) + f(2)
  • f(3) = f(2) + f(1)
  • f(5)를 구하기 위해 이전에 연산을 했던 f(4), f(3), f(2), f(1) 을 다시 해야 한다.
  • 공간복잡도 O(1), 시간복잡도 O(2ⁿ)
• 피보나치 수열 (다이나믹 프로그래밍)
  • f(5) = f(4) + f(3) -> 끝!!!!
  • f(n) 을 구하면 해당 값을 저장하여 반복적인 연산을 줄인다.
  • 공간복잡도 O(n), 시간복잡도 O(n)

계단 n칸을 올라오는 경우의 수는 n-1칸에서 1계단, n-2칸에서 2계단으로 피보나치 수열과 같이 계산하면 된다.

3. 코드

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

        int[] arr = new int[n+1];
        arr[1] = 1; // 계단이 1칸일 경우
        arr[2] = 2; // 계단이 2칸일 경우

        for (int i=3; i<=n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
            System.out.println(arr[i]);
        }

        return arr[n];
    }
}

• 결과 :

Time Submitted	Status	Runtime	Memory	Language
05/03/2021	Accepted	3 ms	36 MB	java

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋