Compute ways to climb n steps
Company: Paradromics
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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).
Quick Answer: 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.