美文网首页
198. 打家劫舍

198. 打家劫舍

作者: 等不了天明等时光 | 来源:发表于2020-03-25 22:04 被阅读0次

解题思路

动态规划:(与面试题17.16按摩师属于同一题型)
定义 dp[i][0] 表示第i家不偷,dp[i][1]表示第i家偷。根据题意,相邻的房屋不能偷。
因此当第i家不偷时,第i-1家偷不偷都可以,则 dp[i][0] = max(dp[i-1][0], dp[i-1][1]);而当第i家偷的时候,第i-1家不能偷,则dp[i][1] = dp[i-1][0]+nums[i],最后返回max(dp[n][0], dp[n][1])即可。
复杂度分析:
时间复杂度:O(n),其中 n 为房屋个数。我们有 2n 个状态需要计算,每次状态转移需要 O(1) 的时间,所以一共需要 O(2n)=O(n) 的时间复杂度。
空间复杂度:O(1),只需要常数的空间存放若干变量。

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp0 = 0 # 第一家不偷
        dp1 = nums[0] # 第一家偷
        for i in range(1, n): # 从第二家开始
            tdp0 = max(dp0, dp1) # 第i家不偷,那么第i-1家可以偷也可以不偷,取最大值
            tdp1 = dp0 + nums[i] # 第i家偷,那么第i-1家不可以偷
            dp0 = tdp0
            dp1 = tdp1
        return max(dp0, dp1)

相关文章

网友评论

      本文标题:198. 打家劫舍

      本文链接:https://www.haomeiwen.com/subject/dvdfuhtx.html