@@ -0,0 +1,1396 @@
+#!/usr/bin/env python%0A%22%22%22%0AYou are a professional robber planning to rob houses along a street. %0AEach house has a certain amount of money stashed, %0Athe only constraint stopping you from robbing each of them is that adjacent houses %0Ahave security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.%0A%0AGiven a list of non-negative integers representing the amount of money of each house, %0Adetermine the maximum amount of money you can rob tonight without alerting the police.%0A%22%22%22%0A%0Aclass Solution(object):%0A    def rob(self, nums):%0A        %22%22%22%0A        :type nums: List%5Bint%5D%0A        :rtype: int%0A%0A        Idea: dynamic programming%0A        could rob house by interval 1 or interval 2, there is no need to rob by interval 3,%0A        because you want rob more money, interval 3 will definitely lose some mony.%0A%0A        dynamic programming equation:%0A        dp%5Bi%5D = max(dp%5Bi - 2%5D, dp%5Bi - 3%5D) + nums%5Bi%5D%0A%0A        Time: O(n)%0A        Space: O(n)%0A        %22%22%22%0A%0A        if nums == None or len(nums) == 0:%0A            return 0%0A%0A        if len(nums) %3C= 2:%0A            return max(nums)%0A        %0A        dp = %5B0 for i in nums%5D%0A%0A        dp%5B0%5D, dp%5B1%5D = nums%5B0%5D, nums%5B1%5D%0A        dp%5B2%5D = dp%5B0%5D + nums%5B2%5D%0A%0A        for i in xrange(3, len(nums)):%0A            dp%5Bi%5D = max(dp%5Bi - 2%5D, dp%5Bi - 3%5D) + nums%5Bi%5D%0A%0A        return dp%5B-1%5D if dp%5B-1%5D %3E dp%5B-2%5D else dp%5B-2%5D%0A

add leetcode 198