How to optimize my solution (time limit exceeded)


  • 0
    B
    def rob(self, nums):
        tmp = nums
        if len(tmp) >= 1:
            max0 = tmp[0]
            if len(tmp) >= 3:
                max0 += self.rob(tmp[2:])
        else:
            max0 = 0
        if len(tmp) >= 2:
            max1 = tmp[1]
            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?


  • 0
    S

    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 self._rob(nums, 2).

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.