SONG Shengjie
List: 198.打家劫舍，213.打家劫舍II，337.打家劫舍III
198.打家劫舍house-robber，213.打家劫舍IIhouse-robber-ii，337.打家劫舍 IIIhouse-robber-iii
198.打家劫舍house-robber
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
dp = [0] * (len(nums))
dp[0] = nums[0]
dp[1] = 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]
213.打家劫舍IIhouse-robber-ii
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
dp = [0] * (len(nums))
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums) - 1):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
result1 = dp[-2]
dp[1] = nums[1]
dp[2] = max(nums[1], nums[2])
for i in range(3, len(nums)):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
result2 = dp[-1]
return max(result1, result2)
337.打家劫舍 IIIhouse-robber-iii
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
result = self.robtree(root)
return max(result[0], result[1])
def robtree(self, cur):
if not cur:
return [0, 0]
leftdp = self.robtree(cur.left)
rightdp = self.robtree(cur.right)
val1 = cur.val + leftdp[0] + rightdp[0]
val2 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1])
return [val2, val1]