[LeetCode] 70 Climbing Stairs

Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

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

Example 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

Constraints:

• 1 <= n <= 45

---

풀이

• 계단은 한 번에 한 칸 또는 두 칸을 오를 수 있으며, 계단을 오르는 방법을 구하는 문제이다.

• DP를 사용하여 푼다.
  계단이 1개일 경우 계단을 오르는 방법은 1개(1칸)이다.
  계단이 2개일 경우 계단을 오르는 방법은 2개(1칸 1칸, 2칸)이다.
  계단이 3개 이상일 경우,
  계단을 오르는 방법 수 = 현재 계단-1 까지 오르는 방법 수 + 현재 계단-2 까지 오르는 방법 수
  로 구할 수 있다.

  F(n) = F(n-1) + F(n-2) => 피보나치 수열

• 계단이 1개 또는 2개일 경우는 계단의 숫자를 반환해주었다.
  계단이 3개 이상일 경우,

• 이 경우는 bottom-up방식으로, 재귀함수를 쓰지 않고 배열만으로 문제를 해결할 수 있다.

• 시간복잡도는 for문을 1개를 n만큼 돌기 때문에 O(N)이다.
  공간 복잡도는 각 계단의 값을 저장할 배열인 O(N)이지만, 현재 계단을 오를 때 필요한 값은 그 이전의 두 계단 뿐이므로 결국 O(1)이다.

---

코드

class Solution {
    public int climbStairs(int n) {
        int[] sumArr = new int[n + 1];

        if (n == 1 || n == 2) {
            return n;
        } else {
            sumArr[0] = 0;
            sumArr[1] = 1;
            sumArr[2] = 2;

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