House Robber

Problem: House Robber

This dynamic programming solution assume that we know the max value we can rob for n-1 houses and for n-2 houses, thus max value for n houses is either former one or latter one plus last house. To justify that, we can first assume we can rob the last house, then seems adding former n-2 houses seems fair to avoid alerting. If we don't rob the last house, the max value may be bigger than former n-1 houses only when max value for n-1 houses equals n-2 houses.

Code in Python:

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp = [nums[0], max(nums[0], nums[1])]
        for i in xrange(2, len(nums)):
            dp.append(max(dp[i-1], dp[i-2] + nums[i]))
        return dp[-1]