[LintCode/LeetCode] House Robber II

OnlyLing 发布于2019-08-14 15:34 / 409人阅读

摘要：因为取了队首就不能取队尾，所以对数组循环两次，一个从取到，一个从取到，比较两次循环后队尾元素，取较大者。注意，要先讨论当原数组位数小于时的情况。

Problem

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.

Notice

This is an extension of House Robber.

Example

nums = [3,6,4], return 6

Note

因为取了队首就不能取队尾，所以对dp数组循环两次，一个从0取到len-2，一个从1取到len-1，比较两次循环后队尾元素，取较大者。注意，要先讨论当原数组位数小于2时的情况。

Solution

public class Solution {
    public int houseRobber2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i <= len-2; i++) dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        int res = dp[len-2];
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i <= len-1; i++) dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        return Math.max(res, dp[len-1]);
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65854.html

[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 评论0 收藏0
[LeetCode] House Robber I II

摘要：注意对边界条件的判断，是否非空，是否长度为 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...

qpal 2019-08-14 15:17 评论0 收藏0
[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原数组上动规，每一行对应一个房子，每一个元素代表从第一行的房子到这一行的房子选择这一种颜色所花的最小开销。所以每个元素该元素的值上一行两个与该元素不同列元素的值的较小者。不过这次要记录三个变量本行最小值，本行第二小值，本行最小值下标。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 评论0 收藏0
leetcode198,213 house robber

摘要：你不能连着偷两家因为这样会触发警报系统。现在有一个数组存放着每一家中的可偷金额，问可以偷的最大金额为多少这里考验了动态编程的思想。动态编程要求我们将问题一般化，然后再找到初始情况开始这个由一般到特殊的计算过程。 House Robber I You are a professional robber planning to rob houses along a street. Each...

whidy 2019-08-16 11:01 评论0 收藏0
[Leetcode] House Robber 打家劫舍

摘要：动态规划复杂度时间空间思路一般来说，给定一个规则，让我们求任意状态下的解，都是用动态规划。另外我们可以做一点优化，本来我们是要用一个数组来保存之前的结果的。所以我们分别算出这两个条件下的最大收益，然后取更大的就行了。可以复用的代码。 House Robber I You are a professional robber planning to rob houses along a ...

golden_hamster 2019-08-14 12:38 评论0 收藏0