198. House Robber

Loading...LeetCode

我以为 easy 题不会有 dp 的...

状态转换方程是 maxRob(n) = max(maxRob(n-2) + nums[n-1], maxRob(n-1)) ，即完整nums不变情况下，n长度的最大rob值是 (n-1)长度的最大rob 和 (n-2)长度最大rob + nums第n项 中的较大值。

写出来的代码感觉不够dp style，改了个第二版，看起来更 dp 了但其实反而没第一版快。

V1

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        if len(nums) <= 2: return max(nums)
        
        dp = {0: 0, 1:nums[0], 2:max(nums[:2])}
        
        def maxRob(n):
            if n in dp: return dp[n]
            curMax = max(maxRob(n-2)+nums[n-1], maxRob(n-1))
            dp[n] = curMax
            return curMax
            
        return maxRob(len(nums))

V2

class Solution:
    def __init__(self):
        self.dp = dict()
        
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: self.dp[0] = 0
        elif n <= 2: self.dp[n] = max(nums)
        if n in self.dp: return self.dp[n]
        curMax = max(self.rob(nums[:n-2])+nums[n-1], self.rob(nums[:n-1]))
        self.dp[n] = curMax
        return curMax