LeetCode講解篇之198. 打家劫舍

題目描述

題解思路

該問題可以通過遞推來完成
遞推公式：
前n間房的最大金額 = max（前n-1間房的最大金額， 前n-2間房的最大金額+第n-1間房的最大金額）

題解代碼

func rob(nums []int) int {if len(nums) == 0 {return 0}n := len(nums)dp := make([]int, n + 1)dp[0] = 0dp[1] = nums[0]for k := 2; k <= n; k++ {if dp[k-1] > dp[k-2] + nums[k-1] {dp[k] = dp[k-1]} else {dp[k] = dp[k-2] + nums[k-1]}}return dp[n]
}