[LintCode/LeetCode] House Robber II

OnlyLing 發布于2019-08-14 15:34 / 519人閱讀

摘要：因為取了隊首就不能取隊尾，所以對數組循環兩次，一個從取到，一個從取到，比較兩次循環后隊尾元素，取較大者。注意，要先討論當原數組位數小于時的情況。

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

GPU云服務器云服務器 Robber House II quartus ii

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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