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 nthstep. 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.
