【附源码】Python ：打家劫舍

系列文章目录

Python 算法学习：打家劫舍问题

文章目录

系列文章目录
一、算法需求
二、解题思路
三、具体方法+源码
- 方法1：动态规划（自底向上）
- 方法2：动态规划（自顶向下）
- 方法3：优化的动态规划
- 方法4：递归
总结

一、算法需求

“打家劫舍”问题是一个经典的动态规划问题，通常用来描述一个小偷在一条街上偷窃房屋的场景。每间房屋都有一定数量的现金，小偷需要决定偷哪些房屋以最大化他的收益。但是，小偷面临一个限制：如果两间相邻的房屋在同一晚上被偷，那么防盗系统会触发报警。因此，小偷不能偷窃相邻的房屋。

二、解题思路

动态规划： 定义一个数组 dp，其中 dp[i] 表示到第 i 间房屋为止能偷到的最大金额。状态转移方程是 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，表示可以选择偷当前房子（前提是不偷前一个房子）或者不偷当前房子（延续前一个房子的决策）。

贪心算法： 虽然不总是最优，但可以作为一种尝试。在每一步选择当前能获得的最大金额，而不考虑未来的房子。

递归： 通过递归函数模拟决策过程，考虑偷或不偷当前房子，并取两种选择中的最大值。

优化空间： 使用两个变量代替数组，减少空间复杂度。

三、具体方法+源码

方法1：动态规划（自底向上）

状态定义：dp[i] 表示到第 i 个房子为止能偷到的最大金额。

计算过程：

dp[0] = 2（只考虑第一个房子）
dp[1] = max(2, 7) = 7（考虑第一个和第二个房子）
dp[2] = max(7, 2+9) = 9（考虑第二个和第三个房子）
dp[3] = max(9, 7+3) = 10（考虑第三个和第四个房子）
dp[4] = max(10, 9+1) = 12（考虑第四个和第五个房子）
结果：12

代码如下：

python">def rob1(nums):if not nums:return 0if len(nums) == 1:return nums[0]dp = [0] * len(nums)dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, len(nums)):dp[i] = max(dp[i-1], dp[i-2] + nums[i])return dp[-1]# 测试
nums = [2, 7, 9, 3, 1]
print("最高金额:", rob1(nums))

方法2：动态规划（自顶向下）

计算过程：

从 rob(0) 开始
rob(1) = max(rob(2), rob(3)) = max(7, 9) = 9
rob(2) = max(rob(3), rob(4) + 2) = max(9, 10) = 10
rob(3) = max(rob(4), rob(5) + 3) = max(9, 12) = 12
rob(4) = max(rob(5), rob(6) + 1) = max(7, 12) = 12
结果：12

代码如下：

python">def rob2(nums):memo = {}def rob(i):if i >= len(nums):return 0if i in memo:return memo[i]memo[i] = max(rob(i+1), nums[i] + rob(i+2))return memo[i]return rob(0)# 测试
nums = [2, 7, 9, 3, 1]
print("最高金额:", rob2(nums))

方法3：优化的动态规划

计算过程：

prev = 2, curr = 7
prev = 7, curr = 9
prev = 9, curr = 10
prev = 10, curr = 12
结果：12

代码如下：

python">def rob3(nums):if not nums:return 0if len(nums) == 1:return nums[0]prev, curr = 0, 0for num in nums:prev, curr = curr, max(prev + num, curr)return curr# 测试
nums = [2, 7, 9, 3, 1]
print("最高金额:", rob3(nums))

方法4：递归

计算过程：

helper(0) = max(helper(1), helper(2) + 2) = max(7, 9) = 9
helper(1) = max(helper(2), helper(3) + 7) = max(9, 10) = 10
helper(2) = max(helper(3), helper(4) + 9) = max(10, 12) = 12
helper(3) = max(helper(4), helper(5) + 3) = max(9, 12) = 12
helper(4) = max(helper(5), 1) = 12
结果：12

代码如下：

python">def rob4(nums):def helper(i):if i == len(nums):return 0if i == len(nums) - 1:return nums[i]return max(helper(i+1), nums[i] + helper(i+2))return helper(0)# 测试
nums = [2, 7, 9, 3, 1]
print("最高金额:", rob4(nums))