資訊專(zhuān)欄INFORMATION COLUMN
摘要：因?yàn)槿×岁?duì)首就不能取隊(duì)尾，所以對(duì)數(shù)組循環(huán)兩次，一個(gè)從取到，一個(gè)從取到，比較兩次循環(huán)后隊(duì)尾元素，取較大者。注意，要先討論當(dāng)原數(shù)組位數(shù)小于時(shí)的情況。
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.
NoticeThis is an extension of House Robber.
Examplenums = [3,6,4], return 6
Note因?yàn)槿×岁?duì)首就不能取隊(duì)尾，所以對(duì)dp數(shù)組循環(huán)兩次，一個(gè)從0取到len-2，一個(gè)從1取到len-1，比較兩次循環(huán)后隊(duì)尾元素，取較大者。注意，要先討論當(dāng)原數(shù)組位數(shù)小于2時(shí)的情況。
Solutionpublic 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]);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65854.html
摘要：解法真的非常巧妙，不過(guò)這道題里仍要注意兩個(gè)細(xì)節(jié)。中，為時(shí)，返回長(zhǎng)度為的空數(shù)組建立結(jié)果數(shù)組時(shí)，是包括根節(jié)點(diǎn)的情況，是不包含根節(jié)點(diǎn)的情況。而非按左右子樹(shù)來(lái)進(jìn)行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...
摘要：注意對(duì)邊界條件的判斷，是否非空，是否長(zhǎng)度為 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...
摘要：在原數(shù)組上動(dòng)規(guī)，每一行對(duì)應(yīng)一個(gè)房子，每一個(gè)元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開(kāi)銷(xiāo)。所以每個(gè)元素該元素的值上一行兩個(gè)與該元素不同列元素的值的較小者。不過(guò)這次要記錄三個(gè)變量本行最小值，本行第二小值，本行最小值下標(biāo)。 Paint House Problem There are a row of n houses, each house can be painted ...
摘要：你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)數(shù)組存放著每一家中的可偷金額，問(wèn)可以偷的最大金額為多少這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問(wèn)題一般化，然后再找到初始情況開(kāi)始這個(gè)由一般到特殊的計(jì)算過(guò)程。 House Robber I You are a professional robber planning to rob houses along a street. Each...
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路一般來(lái)說(shuō)，給定一個(gè)規(guī)則，讓我們求任意狀態(tài)下的解，都是用動(dòng)態(tài)規(guī)劃。另外我們可以做一點(diǎn)優(yōu)化，本來(lái)我們是要用一個(gè)數(shù)組來(lái)保存之前的結(jié)果的。所以我們分別算出這兩個(gè)條件下的最大收益，然后取更大的就行了?？梢詮?fù)用的代碼。 House Robber I You are a professional robber planning to rob houses along a ...
閱讀 2622·2023-04-25 19:47
閱讀 3453·2019-08-29 17:18
閱讀 917·2019-08-29 15:26
閱讀 3417·2019-08-29 14:17
閱讀 1267·2019-08-26 13:49
閱讀 3405·2019-08-26 13:22
閱讀 3124·2019-08-26 10:44
閱讀 2759·2019-08-23 16:51
