Climbing Staircase

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

I remember doing this problem during undergrad/when studying for my AWS internship interviews. I remember the solution being pretty simple after discovering it. I know that it involves dynamic programming (this problem is in the DP category after all).

class Solution {
    public int climbStairs(int n) {
        return climbStairs(n, new HashMap<>());
    }

    public int climbStairs(int n, Map<Integer, Integer> m) {
        if (n < 3) {
            return n;
        }
        if (!m.containsKey(n)) {
            m.put(n, climbStairs(n - 1, m) + climbStairs(n - 2, m));
        }

        return m.get(n);
    }
}

Recent posts from blogs that I like

AI assisted search-based research actually works now

via Simon Willison

Changing Paintings: 67 Circe and her swine

Ulysses visits Circe's island, where his crew are turned into swine. When she tries to do the same with him, he refuses. They marry and spend a year together.

via The Eclectic Light Company

I'm on GitHub Sponsors

If you wanted to give me money but Patreon was causing grief, I'm on GitHub Sponsors now! Help me reach my goal of saving the world from AI scrapers with the power of anime.

via Xe Iaso