题目

描述
你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

分析

可以使用动态规划的原因：考虑前i家能获得的最多金额可以由前i-1 或者i-2家获得

dp[i]: 在考虑前i家的情况下能够获得的最多金额

当不偷第i家时，dp[i]=dp[i-1]
当偷第i家时，dp[i] = dp[i-2] + nums[i-1]
取两者最大值即可

当只有一家时，一定偷，所以dp[1]=nums[0]

代码

class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        # dp[i]:考虑前i家能够获得的最多金额
        dp = [0]*(n+1)
        dp[1] = nums[0]
        for i in range(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
        return dp[n]