蓝桥杯 第5天 动态规划（3）

蓝桥杯 第5天 动态规划（3）

目录

 1.198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com)

（1）菜鸟写法

（2）高手写法

2.213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com)

3.337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

---

 1.198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com) （1）菜鸟写法

这样写也能过，但是局限性很大

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp=[0 for i in range(len(nums)+1)]
        dp[1]=nums[0]
        for i in range(2,len(nums)+1):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
        return dp[-1]

（2）高手写法

这种写法才比较稳健

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:return 0
        if len(nums)==1:return nums[0]
        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-1],nums[i]+dp[i-2])
        return dp[-1]

2.213. 打家劫舍 II - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:return 0
        if len(nums)==1:return nums[0]
        x=self.robs(nums,0,len(nums)-2)
        y=self.robs(nums,1,len(nums)-1)
        return x if x>y else y
    
    def robs(self,nums: List[int],start:int,end:int)->int:
        if(start==end):return nums[start]
        dp=[0]*(len(nums))
        dp[start]=nums[start]
        dp[start+1]=max(nums[start],nums[start+1])
        for i in range(start+2,end+1):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[end]

3.337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

涉及到树了，之前一直用c语言，现在还不懂python对树的 *** 作，留个坑先

# 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: TreeNode) -> int:
        result=self.robtree(root)
        return max(result)
    def robtree(self,node):
        if node==None:
            return(0,0)
        lefts=self.robtree(node.left)
        rights=self.robtree(node.right)
        sto_root=node.val+lefts[1]+rights[1]
        not_sto_root=max(lefts[1],lefts[0])+max(rights[1],rights[0])
        return (sto_root,not_sto_root)