LeetCode198. 打家劫舍
題目描述：
你是一個(gè)專業(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)裝置的情況下华蜒，能夠偷竊到的最高金額辙纬。
有兩種情況：1.你一直偷一直爽，偷到了倒數(shù)第三個(gè)房屋叭喜，當(dāng)你偷完它之后接著偷最后一個(gè)贺拣。2.一直偷到倒數(shù)第二個(gè)房屋（倒數(shù)第三個(gè)沒敢偷），這時(shí)不能偷最后一個(gè)了，因?yàn)橥迪噜彽臅?huì)報(bào)警譬涡。
狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-2]+nums[i], dp[i-1])
Python代碼：
class Solution:
def rob(self, nums):
if len(nums) == 0:
return 0
if len(nums) <= 2:
return max(nums)
dp = [0]*len(nums)
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
return dp[-1]
LeetCode213. 打家劫舍Ⅱ
題目描述：
你是一個(gè)專業(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)裝置的情況下，能夠偷竊到的最高金額甚淡。
先上代碼：
class Solution:
def rob(self, nums):
if len(nums) == 0:
return 0
elif len(nums) <= 2:
return max(nums)
else:
nums1 = nums[:-1]
nums2 = nums[1:]
def rob1(nums):
dp = [nums[0], max(nums[0], nums[1])]
for i in range(2, len(nums)):
dp.append(max(dp[i-2]+nums[i], dp[i-1]))
return dp[len(nums)-1]
return max(rob1(nums1), rob1(nums2))
很簡(jiǎn)單大诸，只需比較從第一個(gè)房屋偷到倒數(shù)第二個(gè)和從第二個(gè)房屋偷到最后一個(gè)哪個(gè)錢多就行了。
LeetCode337. 打家劫舍Ⅲ
題目描述：
上次打劫完一條街道之后和一圈房屋后材诽，你又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)底挫。這個(gè)地區(qū)只有一個(gè)入口，稱之為“根”脸侥。 除了“根”之外建邓，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后睁枕，聰明的你意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”官边。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警外遇。
計(jì)算在不觸動(dòng)警報(bào)的情況下注簿，你一晚能夠盜取的最高金額。
樹形dp問題跳仿，對(duì)于每一個(gè)節(jié)點(diǎn)诡渴，都只有選和不選兩種情況。每次考慮一棵子樹菲语，那么根只有兩種情況妄辩，選和不選。方法dp返回一個(gè)列表山上，dp[0]表示不搶當(dāng)前這個(gè)節(jié)點(diǎn),dp[1]表搶眼耀。
如果搶了,就不能搶它的左右孩子了，即
cur.val+l[0]+r[0]如果沒有搶佩憾，那么哮伟，左右孩子搶不搶都可以干花，取決于哪種情況大，即
max(l)+max(r)
Python代碼：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution：
def dp(self , cur) :
if not cur :
return [0,0]
l = self.dp(cur.left)
r = self.dp(cur.right)
return [max(l)+max(r),cur.val+l[0]+r[0]]
def rob(self, root):
return max(self.dp(root))
