英德市住房城乡建设网站,电子商务网站建设第二版论文,100平米餐馆装修设计,做互联网产品和运营必备的网站系列文章目录
Python 算法学习#xff1a;打家劫舍问题 文章目录 系列文章目录一、算法需求二、解题思路三、具体方法源码方法1#xff1a;动态规划#xff08;自底向上#xff09;方法2#xff1a;动态规划#xff08;自顶向下#xff09;方法3#xff1a;优化的动态…系列文章目录
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, 29) 9考虑第二个和第三个房子 dp[3] max(9, 73) 10考虑第三个和第四个房子 dp[4] max(10, 91) 12考虑第四个和第五个房子 结果12 代码如下 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 代码如下 def rob2(nums):memo {}def rob(i):if i len(nums):return 0if i in memo:return memo[i]memo[i] max(rob(i1), nums[i] rob(i2))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 代码如下 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 代码如下 def rob4(nums):def helper(i):if i len(nums):return 0if i len(nums) - 1:return nums[i]return max(helper(i1), nums[i] helper(i2))return helper(0)# 测试
nums [2, 7, 9, 3, 1]
print(最高金额:, rob4(nums))总结
这个问题在算法学习中非常重要因为它展示了如何使用动态规划解决具有重叠子问题和最优子结构特性的问题。它也常用于面试中考察候选人对动态规划的理解和应用能力。
这个问题的变种也很多比如考虑环形街道的情况或者房屋之间的防盗系统有不同的触发条件等。
