題目

198. 打家劫舍
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2:

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。

分析

設(shè)f(k)為從前k個房子能夠找到最大的金額，Ai為第i個房子的金額

n = 1 f(1) = A1
n = 2 f(2) = max(A1, A2)
n = 3 :

第三個加第一個房子金額（1,2,3,4)

不加保持金額最大(2,1,1,2)

得出動態(tài)方程
f(k) = max(f(k-2) +Ai, f(k-1))

代碼

數(shù)組越界的處理

func rob(nums []int) int {dp := make([]int, len(nums)+2)for i, key := range nums {dp[i+2] = max(dp[i+1], dp[i] + key)}return dp[len(dp)-1] }func max(n, m int) int {if n > m {return n} else {return m} }

這個版本的代碼不太好，沒有用到動態(tài)規(guī)劃的方程。

func rob(nums []int) int {curr := 0prev := 0for _, key := range nums {temp := currcurr = max(prev+key, curr)prev = temp}return curr }func max(n, m int) int {if n > m {return n} else {return m} }

總結(jié)

以上是生活随笔為你收集整理的198. 打家劫舍 golang 动态规划 数组越界的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。