题目:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
链接: 力扣Leetcode—初级算法—动态规划—打家劫舍.
示例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 。
标签:数组、动态规划
思路:
主要Go代码如下:
package main import "fmt" func rob(nums []int) int { n := len(nums) if n == 0 { return 0 } if n == 1 { return nums[0] } if n > 1 { // 如果第一家大于第二家,那么就偷第一家,否则就偷第二家 if nums[1] < nums[0] { nums[1] = nums[0] } if n > 2 { for i := 2; i < n; i++ { // 偷第i家 if nums[i]+nums[i-2] >= nums[i-1] { nums[i] += nums[i-2] } else { // 不偷第i家 nums[i] = nums[i-1] } } } } return nums[n-1] } func main() { a := []int{2, 7, 9, 3, 1} fmt.Println(rob(a)) }
提交截图: