题目描述你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。示例 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和gggf[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(vectorintnums,intbegin,intend){if(beginend)return0;// 区间不存在时没有最大金额intnnums.size();vectorintf(n,0);vectorintg(n,0);f[begin]nums[begin];for(intibegin1;iend;i){f[i]g[i-1]nums[i];g[i]max(f[i-1],g[i-1]);}returnmax(f[end],g[end]);}introb(vectorintnums){intnnums.size();// 选0位置时的最高金额不选0位置时的最高金额之间的最大值returnmax(func(nums,2,n-2)nums[0],func(nums,1,n-1));}};
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和gggf[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(vectorintnums,intbegin,intend){if(beginend)return0;// 区间不存在时没有最大金额intnnums.size();vectorintf(n,0);vectorintg(n,0);f[begin]nums[begin];for(intibegin1;iend;i){f[i]g[i-1]nums[i];g[i]max(f[i-1],g[i-1]);}returnmax(f[end],g[end]);}introb(vectorintnums){intnnums.size();// 选0位置时的最高金额不选0位置时的最高金额之间的最大值returnmax(func(nums,2,n-2)nums[0],func(nums,1,n-1));}};
