Katkat
Back

Compute ways to climb n steps

ParadromicsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This Coding & Algorithms question evaluates recursion and dynamic programming concepts by asking for the count of distinct ways to climb n steps, framed at an algorithmic/implementation level. It is commonly asked because it probes recognition of overlapping subproblems and the ability to optimize naive recursive approaches through subproblem reuse and improved time/space efficiency.

Implement a function that returns the number of distinct ways to reach the top of a staircase with n steps if you can climb either 1 or 2 steps at a time.

  • Input: integer n (assume 1 <= n <= 45)
  • Output: number of distinct ways

Discuss how you would improve a naive recursive solution using dynamic programming (top-down memoization or bottom-up iteration).