class Solution:
    def rob(self , nums: List[int]) -> int:
        dp = [0 for _ in range(len(nums)+1)]

        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])

        return dp[-1]

解决思路

这题的关键是找到状态转移方程。由于对于第i家可以选择偷和不偷，如果偷的话，那么当前的累计值就等于第i-2家的累计值加上当前家的钱；否则就等于第i-1家的累计值。至于偷不偷，则取决于这两种情况哪个偷的钱多，因此需要比较一下他们的大小。则可以得出状态方程为dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])。

复杂度

时间复杂度和空间复杂度都为O（n）。