首页 > 其他分享 >代码随想录day39 || 198 打家劫舍,213 打家劫舍||,337 打家劫舍|||

代码随想录day39 || 198 打家劫舍,213 打家劫舍||,337 打家劫舍|||

时间:2024-08-24 11:15:17浏览次数:11  
标签:return 213 nums int max 随想录 打家劫舍 dp cur

198 打家劫舍

func rob(nums []int) int {
	// 思路,动态规划
	// dp[i] 代表前下标为i能装的最大盗窃物品价值
	// 递推 dp[i] = max(dp[i-1], dp[i-2]+v(i)) // dp[i-1] 代表不偷物品i, dp[i-2]+v(i) 代表偷物品i,那么就不能偷i-1,因为题目要求不能相邻,所以考虑前i-2
	// dp[0] = 0, dp[1] = nums[0]
	// 正序遍历物品
	// print

	var dp = make([]int, len(nums)+1)
	dp[0] = 0
	dp[1] = nums[0]
	for i := 1; i < len(nums); i++ {
		dp[i+1] = max(dp[i], dp[i-1]+nums[i])
	}
	fmt.Println(dp)
	return dp[len(nums)]
}

213 打家劫舍||

func rob(nums []int) int {
	// 相比打家劫舍1 多出一个限制就是首位相连,所以,我们划分两个数组,包含首,以及包含尾,然后对比
	// dp[i] 表示前i个房间偷盗最大金额
	// dp[i] = max(dp[i-1], dp[i-1]+v(i))
	// dp[0]=0, dp[1] = nums[0]
	// 遍历房间
	// print
	length := len(nums)
	if length == 1{
		return nums[0]
	}

	var dp1 = make([]int, length) // 顾首不顾尾
	var dp2 = make([]int, length) // 顾尾不顾首
	dp1[1] = nums[0]
	dp2[1] = nums[1]
	for i := 1; i < length -1 ; i++ {
		dp1[i+1] = max(dp1[i], dp1[i-1]+nums[i])
		dp2[i+1] = max(dp2[i], dp2[i-1]+nums[i+1])
	}
	//fmt.Println(dp1, dp2)
	if dp2[length-1] > dp1[length-1]{
		return dp2[length-1]
	}
	return dp1[length-1]
}

337 打家劫舍|||

image

func rob(root *TreeNode) int {
	// 本题在于树形dp的定义以及递推公式,还要结合树的遍历顺序
	// dp = [2]int{} ,dp[0] 表示不偷取当前节点, dp[1] 表示偷当前节点
	// 递推公式:
	// cur.dp[0] = cur.left.maxdp + cur.right.maxdp   maxdp=max[dp[0],dp[1]]
	// cur.dp[1] = cur.left.dp[0] + cur.right.dp[0] + cur.Val
	// 初始化,空节点dp = [0,0]
	// 树后序遍历
	// print
	res := robTree(root)
	return max(res)
}

func robTree(cur *TreeNode) [2]int {
	var dp = [2]int{}
	if cur == nil {
		return dp
	}

	var leftDP, rightDP [2]int
	// left
	if cur.Left != nil {
		leftDP = robTree(cur.Left)
	}
	// right
	if cur.Right != nil {
		rightDP = robTree(cur.Right)
	}
	// root
	dp[0] = max(leftDP) + max(rightDP)
	dp[1] = leftDP[0] + rightDP[0] + cur.Val
	//fmt.Println(cur.Val, dp[0], dp[1])
	return dp
}
func max(res [2]int) int {
	if res[0] > res[1] {
		return res[0]
	}
	return res[1]
}

标签:return,213,nums,int,max,随想录,打家劫舍,dp,cur
From: https://www.cnblogs.com/zhougongjin55/p/18377551

相关文章

  • 线性dp:大盗阿福(打家劫舍)
    大盗阿福本题与leetcode198题——打家劫舍的题意一模一样,阅读完本文以后可以尝试以下题目力扣题目链接)题目叙述:阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。这条街上一共有N家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两......
  • 「代码随想录算法训练营」第四十五天 | 图论 part3
    目录101.孤岛的总面积DFS思路BFS思路102.沉没孤岛103.水流问题104.建造最大岛屿101.孤岛的总面积题目链接:https://kamacoder.com/problempage.php?pid=1173文章讲解:https://programmercarl.com/kamacoder/0101.孤岛的总面积.html题目状态:看题解DFS思路思路:代码结构......
  • 代码随想录Day24
    93.复原IP地址有效IP地址正好由四个整数(每个整数位于0到255之间组成,且不能含有前导0),整数之间用'.'分隔。例如:"0.1.2.201"和"192.168.1.1"是有效IP地址,但是"0.011.255.245"、"192.168.1.312"和"[email protected]"是无效IP地址。给定一个只包含数字的字符串s......
  • 代码随想录算法训练营第 50 天 |98. 所有可达路径
    代码随想录算法训练营Day50代码随想录算法训练营第50天|98.所有可达路径目录代码随想录算法训练营前言LeetCode98.所有可达路径一、图论基础概念1、图的种类2、度3、连通性:节点的连通情况4、图的构造5、图的遍历方式二、深度优先搜索1、深度优先搜索的三部曲2......
  • 代码随想录算法训练营第 51 天 |LeetCode99岛屿数量 LeetCode100.岛屿的最大面积
    代码随想录算法训练营Day51代码随想录算法训练营第51天|LeetCode99岛屿数量LeetCode100.岛屿的最大面积目录代码随想录算法训练营前言LeetCode200岛屿数量LCR105.岛屿的最大面积一、广度优先搜索基础1、用队列实现2、代码框架:二、卡码网99岛屿数量(LeetCode......
  • 代码随想录算法训练营第 49 天 |LeetCode42 接雨水 LeetCode84 柱状图中最大面积矩形
    代码随想录算法训练营Day49代码随想录算法训练营第49天|LeetCode42接雨水LeetCode84柱状图中最大面积矩形目录代码随想录算法训练营前言LeetCode42接雨水LeetCode84柱状图中最大面积矩形一、LeetCode42接雨水1.题目链接2.思路3.题解二、LeetCode84柱状......
  • 代码随想录算法训练营第 48 天 |LeetCode 739. 每日温度 LeetCode496.下一个更大元素
    代码随想录算法训练营Day48代码随想录算法训练营第48天|LeetCode739.每日温度LeetCode496.下一个更大元素ILeetCode503.下一个更大元素II目录代码随想录算法训练营前言LeetCode739.每日温度LeetCode496.下一个更大元素ILeetCode503.下一个更大元素II一......
  • 24暑假算法刷题 | Day39 | 动态规划 VII | LeetCode 198. 打家劫舍,213. 打家劫舍 II,33
    目录198.打家劫舍题目描述题解213.打家劫舍II题目描述题解337.打家劫舍III题目描述题解打家劫舍的一天......
  • 代码随想录day 38 || 322 零钱兑换,279 完全平方数,139 单词拆分
    322零钱找还funccoinChange(coins[]int,amountint)int{ //装满,并且硬币无限,可以类比完全背包问题 //dp[i][j]表示前i个物品装满容量为j的背包所需要的最少物品数量 //递推公式dp[i][j]=min(dp[i-1][j],dp[i][j-w(i)]+1)//不装物品i的物品数量,装物品i的物品数......
  • 代码随想录DAY22 - 回溯算法 - 08/21
    目录理论回顾什么是回溯法回溯法的效率回溯法解决的问题如何理解回溯组合题干思路和代码递归法递归优化:剪枝组合总和Ⅲ题干思路和代码递归法递归优化电话号码的字母组合题干思路和代码递归法理论回顾什么是回溯法回溯是一种类似枚举的搜索方法,回溯和......