your interviewer

your interviewer just asked you a dynamic programming problem but they said you can't use recursion problem how would you do it don't worry I got you I'm Tara I'm a senior software engineer and I used to teach computer science at Carnegie Mellon we are doing the problem climbing stairs we've covered the algorithm in part 1 we have talked about top down dynamic programming or memoization in part 2 so welcome to part 3 where we talk about bottom up dynamic programming bottom up dynamic programming otherwise known as tabulation if you're new to this problem the goal is to for stair n figure out how many ways to get to stair n by jumping either one stair at a time or two stairs at a time watch part 1 to see the derivation of this recurrence :) our recurrence for this problem looks something like this so this is a recursive problem but you're telling me we can't use recursion what's the deal with that bottom up DP works by taking the recurrence that we'd use in recursion and computing each subproblem iteratively from the ground up bottom up dynamic programming works by taking the recurrence that we'd use in recursion but we compute each subproblem iteratively from the ground up hence bottom up so I drew out the full recursive tree here these are all the different calls we would make if we were computing climb of 5 where n equals 5 so to get climb of 5 we have to first figure out climb of 4 and climb of 3 so on and so forth until we hit these base cases at the bottom where the base cases are one and two for bottom up dynamic programming you can think that we're building the cache from the bottom of the recursive tree all the way up to the top and we reuse what we've computed along the way I'm gonna represent the cache here as a list I'm gonna do n plus 1 values in this cache instead of n you'll see why we use n+1 later so if we were doing top down dynamic programming we would start with climb of 5 we'd be like OK we don't know the answer to climb of 5 we need to figure out climb of 4 first so we'll check that out oh we don't know the answer to climb of 4 we gotta figure out climb of three so on and so forth and of course as you compute answers you save them in a cache and you reuse them instead of recomputing from scratch so the idea of cashing will be quite similar here but instead of starting at the top of this tree we're gonna start at the bottom we all know our base cases off the bat so we're just gonna put them in our cache so we know that climb of one there's only one way to get to one step so it's just one and climb of two is our other base case we don't need to compute anything we just know off the top of our head the climb of two is equal to two so I'm gonna figure out climb of three and I know that climb of one is right here and climb of two is right here so I'm actually just gonna pull those values from our cache to fill in right here climb of three is three so if we pull a value from the cache I'm actually gonna color that green so we pulled both climb of one and climb of two from the cash to get climb of three which is three so now we're looking at climb of four so climb of four is climb of 3 plus climb of two which we have in our cache so we'll actually just grab these from the cash as well no recomputing happening here 2 plus 3 is 5 and that is climb of four alright so then finally to calculate climb of five we have to do climb of 4 plus climb of three so climb of four is right here and climb of three is right here we pull both of those from the cash which is amazing and then because we pulled climb of three from the cash we never even do any other work and we compute finally that 5 plus 3 is equal to eight and in the very end we have figured out the right answer climb of five is equal to eight so even though this is not a recursive problem I wanna treat our two base cases as special edge cases here so we are gonna say if n is less than or equal to 2 return n that's just so we don't get any index out of range errors for our cache which we are actually gonna create right now so the cache just like we did in the write up I'm gonna initialize this with zero and I'm gonna put n plus 1 zeros in a list which you can do in Python with this syntax okay so let's actually fill the cache in with our two base cases and I'm gonna say cache of one is equal to one cache of two is equal to two because we just have those taken care of cool okay so now let's think about our cache actually and I'm gonna draw this out what it might look like for climb of 5 just like we did before so it's gonna look like this right now I need to fill in the rest of my values and I'm gonna need a loop to do that iteratively so we'll say for i in range now where should I start this loop so 3 is our first case where we need to compute the answer so I'm gonna start at 3 and I'm gonna go to n plus 1 cause that makes sure I'll fill in everything here alright so how do I compute climb stairs of 3 using what values we have in our cash right now hint: cache[i] = climbingStairs(i) I'm gonna say the answer is equal to cache of i minus one plus cache of i minus two right because we also need this value that's here and then cash of i minus two that's the second index so here so this would be 5 we fill it into our cash again zero indexed so this would be 5 we fill it into our cash again zero indexed okay do we keep going yes now i equals 5 so once again we do i minus one which is the fourth index look in right here so that's 5 plus the cash at i minus two that's the third index look in right here that's three we would fill that into the fifth spot in our cash again zero indexed cool so in the very end the answer is the last element of our cash we would just return cache at n and that's it that's how you solve a dynamic programming problem with tabulation you first get your recurrence you think about it recursively but then you implement it iteratively and I think it's really helpful to draw out that tree and think about solving the subproblems going up the tree so we're gonna do some harder dynamic programming problems next that's gonna be a really good review for me too so I am looking forward to it so be sure to follow along and thank you so much