目录
1.198. 打家劫舍 - 力扣(LeetCode) (leetcode-cn.com)
(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)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)