Coding questions · Paradromics
Compute ways to climb n steps
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(assume1 <= 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).
Ways to Climb Stairs
Constraints
- 1 <= n <= 45
Examples
Example 1
Input: (1,)
Output: 1
Explanation: One step.
Example 2
Input: (2,)
Output: 2
Explanation: Two ways.
Hints
- ways[n] = ways[n-1] + ways[n-2].