Python实现“打家劫舍“的一种方法你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额解题思路对于每个房屋你有两个选择偷当前房屋那么就不能偷前一个房屋总金额 当前房屋金额 前前个房屋为止的最大金额不偷当前房屋总金额 前一个房屋为止的最大金额状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])class Solution(object): def rob(self, nums): :type nums: List[int] :rtype: int if not nums: return 0 if len(nums) 1: return nums[0] sum_list [nums[0]] sum_list.append(max(nums[0], nums[1])) for i in range(2, len(nums)): sum_list.append(max(sum_list[i - 2] nums[i], sum_list[i - 1])) return sum_list[-1] if __name__ __main__: solution Solution() print (solution.rob([1, 2, 3, 3, 4, 2]))空间优化版本由于只需要前两个状态可以优化空间复杂度到 O(1)def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] prev2 nums[0] # dp[i-2] prev1 max(nums[0], nums[1]) # dp[i-1] for i in range(2, len(nums)): current max(prev1, prev2 nums[i]) prev2 prev1 prev1 current return prev1示例# 示例1 nums [1, 2, 3, 1] print(rob(nums)) # 输出: 4 (偷第1和第3个房屋: 134) # 示例2 nums [2, 7, 9, 3, 1] print(rob(nums)) # 输出: 12 (偷第1、3、5个房屋: 29112)时间复杂度O(n)空间复杂度O(1)
