LeetCode 198&213. House Robber & House Robber II

两题一起

题目:抢劫房屋,不能抢劫相邻的房屋,否则会被抓。升级版的房屋是一个环,也就是最后和最先的房屋是相邻的。

思路:基础版是最简单的动态规划,升级版就是抢最后一间和不抢最后一间的情况取最大的那个。只放基础版的代码了。

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        take = 0
        not_take = 0
        for i,n in enumerate(nums):
            index = i + 2
            temp = take
            take = max(take, not_take + n)
            not_take = max(not_take, temp)

        return take
分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注