姓名域名亞馬遜seo什么意思
LeetCode講解篇之198. 打家劫舍
文章目錄
- 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]
}