【动态规划-BM79 打家劫舍(二)】

题目

BM79 打家劫舍(二)
描述
你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

分析

跟【动态规划-BM78 打家劫舍(一)】的区别是最后一家与第一家相连成环。

这时，第一家与最后一定有一个是一定不取的，分两种情况讨论。

当取第一家时，只需在原有基础上，不要遍历到最后一家即可，ans=dp[n-1]
当不取第一家时，dp[1] = 0, 遍历到最后一家，ans = dp[n]

取两种情况的最大值。

代码

class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        dp = [0]*(n+1)
        # 取第一家
        dp[1] = nums[0]
        # 最后一家不管，不遍历
        for i in range(2,n):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
        # 取到最后一家的前一家
        ans1 = dp[n-1]
        # 不取第一家
        dp = [0]*(n+1)
        # 遍历到最后一家
        for i in range(2,n+1):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
        # 取到最后一家
        ans2 = dp[n]
        return max(ans1,ans2)