Python Solution:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        dp = [0]*(n+1)
        dp[1] = nums[0]
        
        #[2,7,9,3,1,2]
        #dp[i]: largest profit obtained from house 0,1,...,i-1
        #dp[i+1]: largest profit obtained from house 0,1,...,i
        #         1.rob house i, don't touch house i-1, profit: dp[i-1]+nums[i]
        #         2.don't rob house i, profit: dp[i]
        #dp[i+1]=max(dp[i],dp[i-1]+nums[i])
        for i in range(1,n):
            dp[i+1] = max(dp[i],dp[i-1]+nums[i])
            
        return dp[n]
    
    #Time complexity:O(n)
    #Space complexity:O(n)

 

Time Complexity: O(n)

Space Complexity: O(n)

Feeling tired? You can also try our free online no-installation required casual games: Here Please consider to follow my youtube channel to support me: