Dynamic Programming - Tabulation Pt. 3
Revisiting canSum, howSum, and bestSum
Previously we had utilized a top-down recursive strategy to solve our summing algorithms - we recursively call our function until we “bottom” out and reach a base case that we already know the answer to. By using this strategy we could also decide what information to return: a boolean for canSum, an array for howSum, and even add additional logic to determine bestSum. This strategy required us to memoize our results in order to fully optimize the results, thereby reducing unnecessary recursive calls. With tabulation we are using a bottom-up approach where we utilize a table structure that starts with a bottom base case that we use to calculate the next result, reaching our target. We saw this with the fibonacci approach, we built an array the size of our target fibonacci sequence (accounting for the 0th index, our bottom case), and calculate the next index until we reach the end of the array which yields our target. This strategy will be the same blueprint we will use to calculate our summing algorithms.
For our summing algorithm since we will require a nested array to iterate through our numArray, and use those values to fill out our table itself. We know that each of our individual numbers can be derived, so we fill them with a true value. Our individual indices represent possible sums up to the last index which is our target - so we can update our table by traversing index num spaces. Our initial pass will then yield true for all indices corresponding to the numArray. We can then use this to iterate through the rest of the table and return all possible sums.
canSum(7, [3,4,5])
howSum
We can use this technique to solve for the howSum and bestSum algorithms by changing the values we want to store in our table. Since we want to return an array of possible combinations we want to fill our table with null values, with our bottom case in index 0 as an empty array. Then as before, we use the numArray to fill out the table, passing along two values: the original value (starting from the 0th index empty array), and the number of steps required to reach target index.
bestSum
With an additional check for current combination length we can also solve for bestSum. We make sure to check for null values, or whether the existing combination in the array is shorter than our current combination before updating the index.
In all our problem sets some common themes occur:
- Our table length is always our target + 1
- We fill our array with empty values
- Our base case represents the type of data we want to return
- Our last index represents our target and contains our return value