打家劫舍1
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路
动态规划的思路
1 确定dp
dp[i] 指的是有i间房，此时偷取的最高金额
2 确实状态变化规则
dp[i]: 有i间房，偷取的最高金额
dp[i-1] : 有i-1间房，。。。。。
dp[i-2] : 有i-2 间房，。。。。。
value [i] :第i间房的金额
因为不能相邻，dp[i] 和 dp[i-1] 以及dp[i-2]有关
第i间房偷取：dp[i] = dp[i-2] + value[i]
第i间房不偷取： dp[i] = dp [i-1]
dp [i] = max(d[i-1] ,dp[i-2]+value[i]
3 初始化
dp[0] =0
dp[1] = value [0]
4 确定遍历的顺序
从前往后
‘5 举例
。。。。。。
go语言实现
func rob(nums []int) int {
res := make([]int,len(nums)+1)
res[0] = 0 //表示没房的时候，偷取金额为0
res[1] = nums[0]
for i:=2; i<len(res); i++ {
res[i] = max(res[i-1],res[i-2]+nums[i-1])
}
return res[len(nums)]
}
func max(a,b int) int {
if a>b {
return a
} else {
return b
}
}
打家劫舍2
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
思路
这个和上面的类似。
不过要考虑到首尾的情况
1 首部不偷取， 即只需 rob( nums[1:])
2 尾部不偷取，rob （nums[:len(nums)-1)
3 都不偷取， rob(nums[1:len(nums)-1)
1和2 包含第三种情况
动态规划思路和第一个一样
go语言实现
func rob(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
res1 , res2 := 0, 0
res1 = robOne(nums,0,len(nums)-1)
res2 = robOne(nums,1,len(nums))
return max(res1,res2)
}
//把代码抽离出来，避免重复代码
func robOne(nums []int, start,end int) int {
res := make([]int,end-start+1)
res[0] = 0
res[1] = nums[start]
start++
for i:=2; i<len(res); i++ {
res[i] = max(res[i-1],res[i-2]+nums[start])
start++
}
return res[len(res)-1]
}
func max(a,b int) int {
if a>b {
return a
} else {
return b
}
}
打家劫舍3
问题描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
思路
1 二叉树遍历+记忆法
采用中序遍历：根 + 左 + 右
用 resmap 记录遍历过 的树节点
在遍历之前，先判断当前的root（树）是否以及遍历过。
if root== nil {
return 0
}
if _, ok := resmap[root]; ok {
return resmap[root]
}
2 动态规划
一个节点有两个状态，即偷还是不偷，而这个状态有左右子节点所决定，
root： value[x,y] #x是当前节点偷的最大金额，y是不偷
root.Left: value[x1,y1]
root.Right: value[x2,y2]
x = root.val + x1 + x2
y = max(x1,y1) + max(x2,y2)
这里需要用到后序遍历： 左右根
叶子节点往上遍历，
go语言实现
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var resmap = make(map[*TreeNode]int)
func rob(root *TreeNode) int {
res := dan(root)
return max(res[0],res[1])
}
//动态规划
func dan(root *TreeNode) []int {
if root== nil { return []int{0,0} }
left := dan(root.Left)
right := dan(root.Right)
v1 := root.Val + left[0] + right[0]
v2 := max(left[0],left[1]) + max(right[0],right[1])
return []int{v2, v1}
}
func max(a,b int) int {
if a>b {
return a
}
return b
}
//遍历，记忆
func memory(root *TreeNode) int {
if root== nil {
return 0
}
if _, ok := resmap[root]; ok {
return resmap[root]
}
if root.Left==nil && root.Right == nil {
return root.Val
}
value1 := root.Val
if root.Left != nil {
value1 += rob(root.Left.Left) + rob(root.Left.Right)
}
if root.Right != nil {
value1 += rob(root.Right.Left) + rob(root.Right.Right)
}
value2 := rob(root.Left) + rob(root.Right)
resmap[root] = max(value2,value1)
return max(value1,value2)
}
