未分類

House Robber

DynamicProgramming, Go, LeetCode

House Robber

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 you from robbing each of them is that 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.

提示 解題應用
DynamicProgramming 規律觀查

Default:

1
2
3
func rob(nums []int) int {
}

解答思路:

這題卡了滿長一段時間，原因在於不曉得要從何下手，如果是要找偷兩棟不連續的房子求最大值，那只要把所有除了連續狀況遍歷一次就好了，但這題要的不只有單單兩棟，而是不會在相連房子盜取的情況下盡可能去盜取最大資產，所以看來是要換個方式來想，如果只是分成第1、3、5棟全偷再與2、4、6全偷比較兩者誰的多
當然也許有這種狀況，不過實際上有可能出現會1、3、6偷出來的結果會更多，所以如果能一步步模擬會出現的結果，或許就有辦法推出結論:

這邊有一數列為[3, 2, 1, 5]，將其分為左(index奇數)與右(index偶數)來區別，之後只要判斷如果輪到該數而那一側的總合結果比另一側小，這時另一側的總合就能取代原本那一側的總合變成兩側值都一樣，因為另一側index比較小不用擔心相鄰問題，變成可以選擇要繼續往下跳做總合或是往下下個跳(其實就是原本那側的下一個，所以才用取代以方便寫程式)，再分別繼續往下重覆上述動作。

1
2
3
4
	5
1
	2 ← 第二個值進來的時候發現比另一側小
3(此時3可以繼續與1做總合，或是與5做總合[把2取代掉的意思])

程式碼解說:

首先利用迴圈將值一個個取出，接著再藉由index為奇、偶數分為兩側，如果另一側的總合大於輪到該數的那一側，就將另一側的總合取代該側，此時就等於是以另一側為主來找最大值，繼續做下一項的總合或下下項的總合(index比較小不用擔心相鄰問題)，最後跳開迴圈再做最後一次比較兩側的總合，較大的就回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var odd int
var even int
for i, v := range nums {
	if i%2 != 0 {
		odd = odd + v
		if even > odd {
			odd = even
		}
	} else {
		even = even + v
		if odd > even {
			even = odd
		}
	}
}
if odd > even {
	return odd
}
return even

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func rob(nums []int) int {
	var odd int
	var even int
	for i, v := range nums {
		if i%2 != 0 {
			odd = odd + v
			if even > odd {
				odd = even
			}
		} else {
			even = even + v
			if odd > even {
				even = odd
			}
		}
	}
	if odd > even {
		return odd
	}
	return even
}

總結:

要在一數列中找出不連續的極大值總合，訣竅就是將其分為左(index奇數)與右(index偶數)來區別，之後只要判斷如果輪到該數而那一側的總合結果比另一側小，這時另一側的總合就能取代原本那一側的總合變成兩側值都一樣，再分別繼續往下(兩側跳項做總合)重覆上述動作(因另一側index比較小不用擔心相鄰問題)。

分享到