[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

Hint

---

Hint 1

  To reach nth step, what could have been your previous steps? (Think about the step sizes)
	

Code

---

내 제출

---

class Solution {
    public int climbStairs(int n) {
        int a = 0, b = 1;
        for (int i = 0; i < n; ++i) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

Runtime	Memory
0 ms	40.1 MB

다른 풀이

---

class Solution {
    public int climbStairs(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return climbStairs(n, memo);
    }
    
    private int climbStairs(int n, Map<Integer, Integer> memo) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (!memo.containsKey(n)) {
            memo.put(n, climbStairs(n-1, memo) + climbStairs(n-2, memo));
        }
        return memo.get(n);
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/0000-0099/0070.Climbing%20Stairs/Solution.java