def rob(self, nums): tmp = nums if len(tmp) >= 1: max0 = tmp if len(tmp) >= 3: max0 += self.rob(tmp[2:]) else: max0 = 0 if len(tmp) >= 2: max1 = tmp if len(tmp) >= 4: max1 += self.rob(tmp[3:]) else: max1 = 0 return max(max0, max1)
My solution seems to check all combinations of the houses, but I haven't done much dynamic programming so I can't adopt that yet. Any suggestion on what to improve on this?
Instead of operating on a list as input, work with a function that takes: the original input list, untouched, and an index where to start on the list.
So, instead of
self.rob(tmp[2:]), experiment with using
Then, look at the pattern of your function call. Particularly, pay attention to the second argument (index). You'll quickly find that you re-compute the same parameters over and over again.
Now, can you think of a way to, given the same parameters (nums, index), to only compute once per combination?
^ That's the crux of dynamic programming approach.