LeetCode 213. 打家劫舍 II【c++/java详细题解】

x33g5p2x  于10个月前 转载在 C/C++  
字(2.0k)|赞(0)|评价(0)|浏览(93)

1、题目

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

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

示例 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,相邻房间不可偷并且房间是围成一圈的,让我们输出可以偷窃到的最高金额。

样例:

如样例所示,nums = [1,2,3,1],偷窃13,号房间可以获得最高金额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 nn是数组长度。需要对数组遍历一次。

3、c++代码

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]);
    }
};

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

相关文章