Skip to content

198 house robber

198. House Robber

题目: https://leetcode.com/problems/house-robber/

难度:

Easy

状态转移方程:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

AC 代码

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0 : return 0
        elif n == 1 : return nums[0]
        elif n == 2 : return max(nums[0], nums[1])
        else:
            dp = [0 for i in range(n)]
            dp[0] = nums[0]
            dp[1] = max(nums[0],nums[1])
            for i in range(2,n):
                dp[i] = max( dp[i-1], dp[i-2] + nums[i])
        return dp[n-1]
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        last, now = 0, 0
        for i in nums: last, now = now, max(last + i, now)     
        return now


回到顶部