LeetCode 啥題都有：Go 刷「打家劫舍」二
上次刷了一道動(dòng)態(tài)規(guī)劃的題目:Leetcode-198. 打家劫舍I ，今天我們來(lái)看它的進(jìn)階版II。
介紹
這是 House Robber II，也就是 I 的變型版本。II 和 I 的最大區(qū)別在于 II 把房子圍成一個(gè)圈了。這意味著第一幢房子和最后一幢房子是緊挨著的。根據(jù)規(guī)則，兩間相鄰的房子不能同時(shí)偷，對(duì)小偷打擊還是蠻大的。
小偷在不觸發(fā)報(bào)警裝置的情況下，針對(duì)這類場(chǎng)景，如何讓自己偷竊的利益最大化？
解題
上面提到，相鄰兩家不能同時(shí)偷。但是如果只有一家，那么構(gòu)不成相鄰的條件，就偷唯一的那戶人家。
如果有兩家，那么偷的必然是兩家中錢多的那家。
那如果總數(shù)大于 2 家呢？
對(duì)于第 n 家來(lái)說(shuō)，只有兩種選擇:偷或者不偷。
是咋么計(jì)算出當(dāng)前這家是否要偷的呢。
我們假設(shè)當(dāng)前這家編號(hào)為 n，那么，
max(偷第 n 家的錢 + dp[截止第 n-2 家偷的錢], dp[截止第 n-1 家偷的錢])。這才是這道關(guān)于動(dòng)態(tài)規(guī)劃最核心的一個(gè)點(diǎn)。
看懂了嗎？沒(méi)看懂也沒(méi)關(guān)系，手把手摸個(gè)圖片出來(lái)。 
還沒(méi)看懂，加我微信 remember_wuqinqiang 我告訴你。這里順便打個(gè)廣告，沒(méi)加我好友的趕緊加我好友。
最后，還需要考慮一個(gè)問(wèn)題，如何確保偷了第一家就不偷最后一家，偷最后一家就不偷第一家的情況。 很簡(jiǎn)單，直接定義兩個(gè) dp，一個(gè)范圍不包括第一家，一個(gè)范圍不包括最后一家。 最后我們變成了求:
// 偽代碼
最佳偷錢:=max(dp[不包括第一家],dp[不包括最后一家])那么剩下的就是對(duì)兩個(gè) dp 的狀態(tài)轉(zhuǎn)移公式了。
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
if n == 1 {
return nums[0]
}
dp1, dp2 := make([]int, n), make([]int, n)
dp1[0] = nums[0]
dp1[1] = max(dp1[0], nums[1])
dp2[0] = 0 //dp2 不偷第一家
dp2[1] = max(dp2[0], nums[1])
for i := 2; i < n; i++ {
if i < n-1 { // dp1 不偷最后一家
dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
} else {
dp1[i] = dp1[i-1]
}
dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
}
return max(dp2[n-1], dp1[n-1])
}
func max(x int, y int) int {
if x > y {
return x
}
return y
}其實(shí)代碼還能更簡(jiǎn)潔。
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
if n == 1 {
return nums[0]
}
if n == 2 {
return max(nums[0], nums[1])
}
return max(helper(nums[1:]), helper(nums[:n-1]))
}
func helper(nums []int) int {
first, second := nums[0], max(nums[0], nums[1])
for _, v := range nums[2:] {
first, second = second, max(second, first+v)
}
return second
}
func max(a, b int) int {
if a > b {
return a
}
return b
}今天的題就分享到這了。
推薦閱讀