朝阳淘宝网站建设网上教育培训机构

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