0070 Climbing Stairs

Warning

This post is more than a year old. Information may be outdated.

Solved at: 230128

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

Question

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?

Solution

class Solution {
    func climbStairs(_ n: Int) -> Int {
        var map = [0: 1, 1: 1]
        if map.keys.contains(n) {
            return map[n]!
        }
        for i in 2...n {
            map[i] = map[i-1]! + map[i-2]!
        }
        return map[n]!
    }
}

Results

Runtime 0 ms, Beats 100%
Memory 13.7 MB, Beats 67.32%

Complexity Analysis

$O(n)$ for both

Takeaways

Using Fibonacci will give $O(1)$ space complexity.

Coding Tests