[LeetCode] 70. Climbing Stairs

Problem

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

Solution

Logic

• 변수 n에 따라 반환해야 하는 값은 아래 표와 같다. (0은 계산 편의상 추가)

|n|반환 값|Equals| |:—:|:—:|:—:| |0|1|1| |1|1|1| |2|2|1 + 1| |3|3|1 + 2| |4|5|2 + 3| |5|8|3 + 5| |6|13|5 + 8| |…|…|…|

• n이 2이상일 때부터 반환해야 하는 값은 n - 1일 때 반환해야 하는 값과 n - 2일 때 반환해야 하는 값의 합과 같다. n에 따라 반환해야 하는 값은 피보나치 수열을 이룬다.

  Code(Array Memo)

  class Solution {
    public int climbStairs(int n) {
        int[] cnt = new int[n + 1];
        cnt[0] = 1;
        cnt[1] = 1;
        for (int i = 2; i < cnt.length; i++)
            cnt[i] = cnt[i - 2] + cnt[i - 1];
        return cnt[n];
    }
  }
  

  Code(Var Memo)

  class Solution {
    public int climbStairs(int n) {
        int prev1 = 0, prev2 = 1;
        int cnt = 0;
        for (int i = 1; i < n + 1; i++) {
            cnt = prev1 + prev2;
            prev1 = prev2;
            prev2 = cnt;
        } return cnt;
    }
  }
  

  Time Complexity

• 변수 n의 크기를 n이라 가정할 때, 아래 반복문은 O(n)의 시간 복잡도를 갖는다. 따라서 본 문제는 O(n)의 시간 복잡도를 가진다.

  int[] cnt = new int[n + 1];
  cnt[0] = 1;
  cnt[1] = 1;
  for (int i = 2; i < cnt.length; i++)
    cnt[i] = cnt[i - 2] + cnt[i - 1];