def rob(self, nums):
        """
        Two cases: cannot touch 1st element vs. cannot touch 2nd element.
        There are two cases here 1) 1st element is included and last is not included 2) 1st is not included and last is
        included.
        :type nums: list
        :rtype: int
        """
        n = len(nums)
        if n < 2:
            return sum(nums)

        # include first but exclude last
        dp = [0 for _ in xrange(n-1+2)]
        for i in xrange(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-2])
        ret = dp[-1]

        # exclude first but include last
        dp = [0 for _ in xrange(n-1+2)]
        for i in xrange(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])

        ret = max(ret, dp[-1])
        return ret
dataset/ETHPy150Open algorhythms/LeetCode/213 House Robber II.py/Solution.rob/original