213. 打家劫舍 II

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

算法思想

这道题和打家劫舍 I的唯一区别就是所有房屋围成一圈，第一个房屋和最后一个房屋相邻。因此可以把这道题转换成打家劫舍 I

对于下标为000的屋子，可以偷也可以不偷：

• 如果偷了下标为000屋子，那下标为111的屋子和下标为n−1n-1n−1的屋子就不能偷，因此答案就是在[2,n−2][2, n-2][2,n−2]区间上做打家劫舍 I，得到最大金额，再加上nums[0]nums[0]nums[0]

• 如果下标为000的屋子，那下标为111的屋子和下标为n−1n-1n−1的屋子是能偷的，因此答案就是在[1,n−1][1, n-1][1,n−1]区间上做打家劫舍 I得到的最大金额

• 最终答案就是它们之间的最大值

对于打家劫舍 I，思路如下：

创建dpdpdp数组，确定状态表示：以iii为结尾，dp[i]dp[i]dp[i]就表示到达iii位置时的最高金额，由于iii位置可偷可不偷，所以继续细分，创建两个数组fff和ggg，f[i]f[i]f[i]表示偷了iii位置后的最大金额，g[i]g[i]g[i]表示不偷iii位置时的最大金额

推导状态转移方程：对于f[i]f[i]f[i]，它要偷iii位置，所以f[i]f[i]f[i]应该等于[0,i−1][0, i-1][0,i−1]区间上的最大金额再加上nums[i]nums[i]nums[i]。既然偷了iii位置，i−1i-1i−1位置肯定不偷，所以[0,i−1][0, i - 1][0,i−1]区间上的最大金额就是g[i−1]g[i-1]g[i−1]，f[i]=g[i−1]+nums[i]f[i] = g[i-1] + nums[i]f[i]=g[i−1]+nums[i]。对于g[i]g[i]g[i]，它不偷iii位置，所以i−1i-1i−1位置可偷可不偷，如果偷了，g[i]=f[i−1]g[i] = f[i-1]g[i]=f[i−1]，也就是偷了i−1i-1i−1位置的最大金额，如果不偷，g[i]=g[i−1]g[i] = g[i-1]g[i]=g[i−1]，也就是不偷i−1i-1i−1位置的最大金额，g[i]g[i]g[i]要的是最大值，所以g[i]=max(g[i−1],f[i−1])g[i] = max(g[i-1], f[i-1])g[i]=max(g[i−1],f[i−1])

初始化：根据状态转移方程，f[0]f[0]f[0]和g[0]g[0]g[0]填的时候会越界，要初始化，由于f[0]f[0]f[0]表示偷了000位置的最大金额，所以f[0]=nums[0]f[0] = nums[0]f[0]=nums[0]，g[0]g[0]g[0]表示不偷000位置的最大金额，前面没有其他值了，所以g[0]=0g[0] = 0g[0]=0

填表顺序：从左到右，两个一起填

返回值：max(f[n−1],g[n−1])max(f[n-1], g[n-1])max(f[n−1],g[n−1])

代码

classSolution{public:intfunc(vector<int>&nums,intbegin,intend){if(begin>end)return0;// 区间不存在时，没有最大金额intn=nums.size();vector<int>f(n,0);vector<int>g(n,0);f[begin]=nums[begin];for(inti=begin+1;i<=end;++i){f[i]=g[i-1]+nums[i];g[i]=max(f[i-1],g[i-1]);}returnmax(f[end],g[end]);}introb(vector<int>&nums){intn=nums.size();// 选0位置时的最高金额，不选0位置时的最高金额之间的最大值returnmax(func(nums,2,n-2)+nums[0],func(nums,1,n-1));}};