LeetCode 198. 打家劫舍

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

方法：动态规划

• 若数组 nums 不存在，即没有房屋，那么最高偷窃金额一定为零
• 若数组 nums 的长度为 1，即只有一个房屋，那么最高偷窃金额即为该房屋的金额
• 若数组 nums 的长度大于等于2，即存在两个或两个以上房屋
  • dp[i] 表示下标为 i 且 i 以内的房屋，最高偷窃金额
  • 根据题目定义，不能同时偷窃两个相邻的房屋。初始化 dp[0] 为下标为 0 的房屋的金额，dp[1] 为下标为 0 的房屋的金额和下标为 1 的房屋的金额的最大值
  • 从前向后进行遍历，若偷下标为 i 的房屋，那么最高偷窃金额为 dp[i-2] + nums[i]；若不偷下标为 i 的房屋，那么最高偷窃金额为 dp[i-1]
    ※ 因为 dp 数组随着下标的增加，下标对应的数值是非递减的。在决定偷窃 i 房屋时，并不代表一定会偷窃 i-2 房屋

class Solution(object):
    def rob(self, nums):
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp = [0] * len(nums)
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[-1]

参考

代码相关：https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html