LeetCode高频面试题|LeetCode 213. 打家劫舍 II【c++/java详细题解】 c++|java|动态规划|leetcode

- - 1、题目
  - 2、思路
  - 3、c++代码
  - 4、java代码

1、题目
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
【LeetCode高频面试题|LeetCode 213. 打家劫舍 II【c++/java详细题解】】示例 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

2、思路
给定一个代表金额的非负整数数组nums，相邻房间不可偷并且房间是围成一圈的，让我们输出可以偷窃到的最高金额。
样例：

LeetCode高频面试题|LeetCode 213. 打家劫舍 II【c++/java详细题解】

文章图片
如样例所示，nums = [1,2,3,1]，偷窃1，3，号房间可以获得最高金额4。
打家劫舍 I
我们先来看看「198. 打家劫舍」房间单排排列的动态规划的做法。
状态表示：f[i]表示偷窃1号到i号房间所能获得的最高金额。那么，f[n]就表示偷窃1号到n号房间所能获得的最高金额，即为答案。
状态计算：
假设有i间房间，考虑最后一间偷还是不偷房间，有两种选择方案：

1、偷窃前i-1间房间，不偷窃最后一间房间，那么问题就转化为了偷窃1号到i- 1号房间所能获得的最高金额，即f[i] = f[i-1]。

文章图片

2、偷窃前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、不偷窃最后一间房间，那么问题转化为偷窃1号到i - 1号房间所能获得的最高金额。
2、不偷窃第一间房间，那么问题转化为偷窃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是数组长度。需要对数组遍历一次。
3、c++代码

class Solution { public: int rob(vector& nums) { int n = nums.size(); if(n == 1) return nums[0]; //只有一间房间，返回nums[0] vectorf(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]); } };

4、java代码

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