摘要：给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。状态表示表示偷窃号到号房间所能获得的最高金额。下标均从开始打家劫舍我们已经知道了房间单排排列的状态转移方程，接下来思考房间环状排列的做法。
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]输出：3解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
输入：nums = [1,2,3,1]输出：4解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。示例 3：
输入：nums = [0]输出：0给定一个代表金额的非负整数数组nums，相邻房间不可偷并且房间是围成一圈的，让我们输出可以偷窃到的最高金额。
样例：
如样例所示，nums = [1,2,3,1]，偷窃1，3，号房间可以获得最高金额4。
打家劫舍 I
我们先来看看「198. 打家劫舍」房间单排排列的动态规划的做法。
状态表示：f[i]表示偷窃1号到i号房间所能获得的最高金额。那么，f[n]就表示偷窃1号到n号房间所能获得的最高金额，即为答案。
状态计算：
假设有i间房间，考虑最后一间偷还是不偷房间，有两种选择方案：
i-1间房间，不偷窃最后一间房间，那么问题就转化为了偷窃1号到i- 1号房间所能获得的最高金额，即f[i] = f[i-1]。i - 2间房间和最后一间房间 (相邻的房屋不可闯入)，那么问题就转化为了偷窃1号到i- 2号房间所能获得的最高金额再加上偷窃第i号房间的金额，即f[i] = f[i - 2] + nums[i]。 (下标均从1开始)两种方案，选择其中金额最大的一个。因此状态转移方程为： f[i] = max(f[i - 1], f[i - 2] + nums[i])。 (下标均从1开始)
打家劫舍 II
我们已经知道了房间单排排列的状态转移方程，接下来思考房间环状排列的做法。
房间环状排列 意味着第一间和最后一间不能同时选择，因此我们可以分成两种情况来讨论：
1号到i - 1号房间所能获得的最高金额。2号到i号房间所能获得的最高金额。两种情况中取最大值，这样我们就把环状排列问题转化为了两个单排排列的子问题。
我们定义两个数组f[]和g[]，分别用f[n-1]和g[n]两个数组值来表示区间[1, n - 1]和[2, n]的最大金额值，图示过程如下：
初始化：
f[1] = nums[0]，只偷窃1号房间所能获得的最高金额为nums[0]。
g[2] = nums[1]，把第二间房间当成房间单排排列的起点，只偷窃2号房间所能获得的最高金额为nums[1]。
实现细节：
我们定义的状态表示f[]、g[]数组以及nums[]数组下标均是从1开始的，而题目给出的nums[]数组下标是从0开始的。为了一 一对应，状态转移方程中的nums[i]的值要往前错一位，取nums[i - 1]，这点细节希望大家可以注意一下。
时间复杂度分析： O ( n ) O(n) O(n)，其中 n n n是数组长度。需要对数组遍历一次。
class Solution {public: int rob(vector<int>& nums) { int n = nums.size(); if(n == 1) return nums[0]; //只有一间房间，返回nums[0] vector<int>f(n + 1), g(n + 1); f[1] = nums[0], g[2] = nums[1]; //初始化 for(int i = 2; i <= n - 1; i++) f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]); //区间[1,n-1]最大值 for(int i = 3; i <= n; i++) g[i] = max(g[i - 1], g[i - 2] + nums[i - 1]); //区间[2,n]最大值 return max(f[n - 1], g[n]); }};class Solution { public int rob(int[] nums) { int n = nums.length; if(n == 1) return nums[0]; //只有一间房间，返回nums[0] int[] f = new int[n + 1], g = new int[n + 1]; f[1] = nums[0]; //初始化 g[2] = nums[1]; for(int i = 2; i <= n - 1; i++) f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]); for(int i = 3; i <= n; i++) g[i] = Math.max(g[i - 1], g[i - 2] + nums[i - 1]); return Math.max(f[n - 1], g[n]); }}原题链接：213. 打家劫舍 II
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/120811.html
摘要：偷窃到的最高金额。世纪年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。 showImg(https://segmentfault.com/img/bVbplM3?w=953&h=465); 题目描述 你是一个专业的小偷，计划偷窃沿街的房屋，每间房...
摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...
摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。 一 目录 不折腾的前端，和咸鱼有什么区别...
摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...
摘要：字符数值例如，罗马数字写做，即为两个并列的。通常情况下，罗马数字中小的数字在大的数字的右边。给定一个罗马数字，将其转换成整数。 Create by jsliang on 2019-05-23 13:24:24 Recently revised in 2019-05-23 14:55:20 一 目录 不折腾的前端，和咸鱼有什么区别 目录 一 目录 二 前言 三 解题 ...
阅读 2088·2021-11-05 09:42
阅读 2819·2021-09-23 11:21
阅读 2813·2019-08-30 14:00
阅读 3292·2019-08-30 13:15
阅读 444·2019-08-29 17:18
阅读 3518·2019-08-29 16:29
阅读 2714·2019-08-29 14:06
阅读 2778·2019-08-23 14:41
