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]
}