Dynamic Programming: Bottom-Up

bottom-up iterative approach
exampleN = 10 (our target value)K = [1, 5, 10] (our array of coins)There are 4 different ways to make 10 cents.
our base case would be
[[1,1,1],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0],[1,0,0]]
red boxes are solved. solid blue box is the 5 into 1, which is 0.
k-1 is 1 (circled)
dp[n][k] = (dp[n] / dp[k]) + dp[n][k-1]
using the coin itself(dark blue) and using the previous coins possible solutions
setting up our base case is complete
dp[i][j] = (i / k[j]) + dp[i][j-1]since i represents n and k[j] represents the current coin
return dp[-1][-1] 
# -1 get the last item of the array.
# dp[-1] is [1,3,4]
# dp[-1][-1] is 4
using dp[-1][-1] we can target the last “box” which is 4

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store