Climbing Stairs
Transitions
Observe that for every stair, you can make two decisions:
Climb one step
Climb two steps
Recurrence tree
Top-down
Top-down can often be implemented by directly modelling the state transitions
The recurrence relation above looks like this:
Bottom-up
Trick: Re-framing the problem A way to convert top-down to bottom-up solutions is to re-frame the problem in a way that only restricts your view of the data to a subset, such as the prefix/suffix/sub-array. Solving this subset gives you the tools to solve larger subsets. A good way to do this is to ask: "Given index i, how do I use the solutions of 0 to i-1 (prefix) or i+1 to n (suffix) solve for index i?"
Optimization
From the recurrence relation, we only ever require the previous 2 states, dp(m - 1)
and dp(m - 2)
to compute dp(m)
. So, we can store these 2 states as variables instead of using an array.
Keen observers will notice that this is basically the Fibonacci sequence
Last updated