F*** you, Dynamic Programming!

num_ways(10) = num_ways(4) + num_ways(5) + num_ways(7) + num_ways(8)
def num_ways(x):
if x < 2: return 0 # base case
ways = num_ways(x-6) + num_ways(x-5)
+ num_ways(x-3) + num_ways(x-2)
if x in c: ways += 1
return ways
num_ways(7) = num_ways(1) + num_ways(2) + num_ways(4) + num_ways(5)
def num_ways(x):
if ways[x] is NULL:
ways[x] = do_recursive_call()
return ways[x]
num_ways(10, [2,3,5,6]) = num_ways(4, [6]) # used 6$, so can't use 2$ or 3$ or 5$
+ num_ways(5, [5, 6])
+ num_ways(7, [3, 5, 6])
+ num_ways(8, [2, 3, 5, 6]) # used 2$, so can use 2$, 3$, 5$ as-well

--

--

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