打家劫舍1
問(wèn)題描述
你是一個(gè)專(zhuān)業(yè)的小偷落塑，計(jì)劃偷竊沿街的房屋纽疟。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)芜赌，如果兩間相鄰的房屋在同一晚上被小偷闖入仰挣，系統(tǒng)會(huì)自動(dòng)報(bào)警伴逸。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組缠沈，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額错蝴。
思路
動(dòng)態(tài)規(guī)劃的思路
1 確定dp
dp[i] 指的是有i間房洲愤，此時(shí)偷取的最高金額
2 確實(shí)狀態(tài)變化規(guī)則
dp[i]: 有i間房，偷取的最高金額
dp[i-1] : 有i-1間房顷锰，柬赐。。官紫。肛宋。州藕。
dp[i-2] : 有i-2 間房，酝陈。床玻。。沉帮。锈死。
value [i] :第i間房的金額
因?yàn)椴荒芟噜彛琩p[i] 和 dp[i-1] 以及dp[i-2]有關(guān)
第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語(yǔ)言實(shí)現(xiàn)
func rob(nums []int) int {
res := make([]int,len(nums)+1)
res[0] = 0 //表示沒(méi)房的時(shí)候，偷取金額為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
問(wèn)題描述
你是一個(gè)專(zhuān)業(yè)的小偷渗常，計(jì)劃偷竊沿街的房屋壮不，每間房?jī)?nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都 圍成一圈 皱碘，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的询一。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)癌椿，如果兩間相鄰的房屋在同一晚上被小偷闖入健蕊，系統(tǒng)會(huì)自動(dòng)報(bào)警 。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組踢俄，計(jì)算你 在不觸動(dòng)警報(bào)裝置的情況下 缩功，今晚能夠偷竊到的最高金額。
思路
這個(gè)和上面的類(lèi)似都办。
不過(guò)要考慮到首尾的情況
1 首部不偷取嫡锌， 即只需 rob( nums[1:])
2 尾部不偷取，rob （nums[:len(nums)-1)
3 都不偷取琳钉， rob(nums[1:len(nums)-1)
1和2 包含第三種情況
動(dòng)態(tài)規(guī)劃思路和第一個(gè)一樣
go語(yǔ)言實(shí)現(xiàn)
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)
}
//把代碼抽離出來(lái)势木，避免重復(fù)代碼
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
問(wèn)題描述
小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口歌懒，我們稱(chēng)之為 root 啦桌。
除了 root 之外，每棟房子有且只有一個(gè)“父“房子與之相連及皂。一番偵察之后甫男，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類(lèi)似于一棵二叉樹(shù)”且改。 如果 兩個(gè)直接相連的房子在同一天晚上被打劫 ，房屋將自動(dòng)報(bào)警板驳。
給定二叉樹(shù)的 root 钾虐。返回 在不觸動(dòng)警報(bào)的情況下 ，小偷能夠盜取的最高金額 笋庄。
思路
1 二叉樹(shù)遍歷+記憶法
采用中序遍歷：根 + 左 + 右
用 resmap 記錄遍歷過(guò) 的樹(shù)節(jié)點(diǎn)
在遍歷之前效扫，先判斷當(dāng)前的root（樹(shù)）是否以及遍歷過(guò)。
if root== nil {
return 0
}
if _, ok := resmap[root]; ok {
return resmap[root]
}
2 動(dòng)態(tài)規(guī)劃
一個(gè)節(jié)點(diǎn)有兩個(gè)狀態(tài)直砂，即偷還是不偷菌仁，而這個(gè)狀態(tài)有左右子節(jié)點(diǎn)所決定，
root： value[x,y] #x是當(dāng)前節(jié)點(diǎn)偷的最大金額静暂，y是不偷
root.Left: value[x1,y1]
root.Right: value[x2,y2]
x = root.val + x1 + x2
y = max(x1,y1) + max(x2,y2)
這里需要用到后序遍歷： 左右根
葉子節(jié)點(diǎn)往上遍歷济丘，
go語(yǔ)言實(shí)現(xiàn)
/**
* 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])
}
//動(dòng)態(tài)規(guī)劃
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)
}
