在线音乐网站开发,wordpress数据库结构图,做网站导航一般字号是多少,泗洪网站建设第九章 动态规划 198.打家劫舍213.打家劫舍II337.打家劫舍III代码随想录文章详解 198.打家劫舍
dp[i]表示偷第i家及之前所能获取的最大金额 偷第i家#xff1a;dp[i] dp[i-2]nums[i]#xff0c;不偷第i家#xff1a;dp[i] dp[i-1]
func rob(nums []int) int {if len(num… 第九章 动态规划 198.打家劫舍213.打家劫舍II337.打家劫舍III代码随想录文章详解 198.打家劫舍
dp[i]表示偷第i家及之前所能获取的最大金额 偷第i家dp[i] dp[i-2]nums[i]不偷第i家dp[i] dp[i-1]
func rob(nums []int) int {if len(nums) 0 {return 0}if len(nums) 1 {return nums[0]}dp : make([]int, len(nums))dp[0] nums[0]dp[1] max(nums[0], nums[1])for i : 2; i len(nums); i {dp[i] max(dp[i-1], dp[i-2]nums[i])}return dp[len(nums) - 1]
}因为抢劫到的最高金额只与前两间房屋有关故采用滚动数组优化
first : nums[0]second : max(nums[0], nums[1])for i : 2; i len(nums); i {temp : secondsecond max(firstnums[i], second)first temp}return second213.打家劫舍II
上题扩展房屋是环状的意味着第一个房子和最后一个房子不能同时偷故求解max(不偷第一个房子不偷最后一个房子)
func rob(nums []int) int {if len(nums) 0 {return 0}if len(nums) 1 {return nums[0]}if len(nums) 2 {return max(nums[0], nums[1])}return max(rob1(nums[1:]), rob1(nums[:len(nums)-1]))
}func rob1(nums []int) int {first : nums[0]second : max(nums[0], nums[1])for i : 2; i len(nums); i {temp : secondsecond max(firstnums[i], second)first temp}return second
}337.打家劫舍III
后序遍历通过递归函数的返回值进行下一步求解 偷当前节点则当前节点的左右孩子都不能偷不偷当前节点则当前节点的左右孩子可偷可不偷取两种可能性的最大值。
func rob(root *TreeNode) int {var help func(root *TreeNode) (int, int)help func(root *TreeNode) (int, int) {if root nil {return 0, 0}leftRob, leftNoRob : help(root.Left)rightRob, rightNoRob : help(root.Right)rob : root.Val leftNoRob rightNoRobnoRob : max(leftRob, leftNoRob) max(rightRob, rightNoRob)return rob, noRob}return max(help(root))
}代码随想录文章详解
198.打家劫舍 213.打家劫舍II 337.打家劫舍III
