企业官网建设流程全解析

Python实现“打家劫舍“的一种方法

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

解题思路

对于每个房屋，你有两个选择：

1. 偷当前房屋：那么就不能偷前一个房屋，总金额 = 当前房屋金额 + 前前个房屋为止的最大金额

2. 不偷当前房屋：总金额 = 前一个房屋为止的最大金额

状态转移方程：

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个房屋: 1+3=4) # 示例2 nums = [2, 7, 9, 3, 1] print(rob(nums)) # 输出: 12 (偷第1、3、5个房屋: 2+9+1=12)

时间复杂度：O(n)，空间复杂度：O(1)