70. Climbing Stairs

Climbing Stairs - LeetCodeLeetCode

This is a 1D array dynamic programming problem. It can be solved in both Bottom-Up and Top-Down approach.

This is a good problem to get started on the basics of 1D DP problems.

Problem Description

The question is in how many ways we can reach the $n^{th}$step. The valid moves are at any given step is 1 or 2 moves. And need to make sure that we do not go out of bounds

Intuition

Top Down

In the above recursion tree, we see there are duplicate computations

The dotted lines represent the duplicate computations. In DP, we optimize it by storing them in a cache, so we make sure we compute the value only once and rest of the calls for that function gets picked up from cache.

Solution