[LeetCode] 213. House Robber II

本文主要是介绍[LeetCode] 213. House Robber II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/house-robber-ii/description/

题目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).Total amount you can rob = 1 + 3 = 4.

思路

题目大意

求一条环路上的所求最大和，求和时，环路两个相邻的元素不能同时计算。

解题思路

基于 198. House Robber 问题 的变型。
总体解法还是 House Robber 的dp。最后结果为 nums[0:nums.length-2] 与 nums[1:nums.length-1] 的House Robber 解 的 较大值。
这是因为 nums[0] 和 nums[nums.length-1] 同时只有一个可以加和。

class Solution {public int rob(int[] nums) {if(nums.length == 1)    return nums[0];return Math.max(eachRob(nums,0,nums.length-2),eachRob(nums,1,nums.length-1));}public int eachRob(int[] nums,int first,int last){int a = 0,b = 0;for(int i = first; i<=last;i++){int c = Math.max(a+nums[i],b);a = b;b = c;}return b;}     
}

这篇关于[LeetCode] 213. House Robber II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---