Python每日一练-----打家劫舍plus

⛅（day14）

目录

🖍题目：

题目分析：

解题思路：

🌈动态规划解法

🌈代码注释

 🌈优化

前言：没看过打家劫舍的可以先看看更容易理解plus版

Python每日一练-----打家劫舍_亖夕的博客-CSDN博客

🖍题目：

假设你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
现在防盗系统升级，第一间房子和最后一间房子防盗系统互通，当同时盗取第一间房子和第二间房子是会触法警报。

给定一个代表每个房屋存放金额的非负整数数组nums，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。（1 <= nums.length <= 100）

🌠示例 1:

输入：nums = [2,3,2]
输出：3
说明：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

🌠示例 2:

输入：nums = [1,2,3,1]
输出：4
说明：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

🌠示例 2:

输入：nums = [1,2,3]
输出：3

题目分析：

在k个房子中，每个房子有不同数量的现金，你需要在不触发警报的情况下拿到最多的金额。警报出发的条件是盗取相邻两间房子，这意味着你不能盗取相邻的两间房子。还有就是不能同时盗取第一和最后一间房子。

解题思路：

从题目可以看出这是一道比较典型的动态规划题目

上动态规划五部曲

✨1.分析确定dp数组以及其下标的含义

（dp数组是什么？

（1）DP是dynamic programming的缩写，中文为动态规划编程，是一种编程思想。
（2）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。用一个表来记录所有已经解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。）

现在确定dp[i]表示从盗取的第一间房间到盗取的第i间房间可以获得的最大金额

✨2.确定递推公式 

（1）偷第i间房子,那么第i-1间房子是不需考虑的

那么     dp[i] = dp[i-2] + nums[i]

nums[i]为第i间房间盗取的金额，dp[i-2]表示从盗取的第一间房间到盗取的第i-2间房间可以获得的最大金额

（2）如果不偷第i间房子，偷第i-1间房子

那么    dp[i] = dp[i-1]

可能有同学会问为什么不是  dp[i] = dp[i-1] + nums[i-1]?

这时因为dp[i]表示的是从盗取的第一间房间到盗取的第i间房间可以获得的最大金额

这时候的dp[i-1] 表示从盗取的第一间房间到盗取的第i-1间房间可以获得的最大金额

展开就是dp[i-1] = dp[i-3] + nums[i-1]

（3）plus的关键在于第一间和最后一间

这里分两种情况

一：偷第一间

递推公式不变，只需遍历第一间到倒数第二间

二：偷最后一间

递推公式不变，只需遍历第二间到最后一间

✨3.如何初始化dp数组

从公式dp[i] = dp[i-2] + nums[i]可知，dp[i]的基础是dp[0],和dp[1]

因为dp[0] = dp[0]     dp[1] = max(dp[0], dp[1])    dp[2] = max(dp[1], dp[0]+nums[2])

✨4.确定遍历的顺序

由dp[i]的定义，以及公式dp[i]有dp[i-2],和dp[i-1]推导出来（上诉两种情况共同决定dp[i]），所以遍历顺序为左到右。

✨5.举例验证推导的dp数组（公式）是否正确

比如可以以例一为例

图解·

 

代码实现

🌈动态规划解法

def rob(nums):    if len(nums) == 1: return nums[0] # 不偷第一间    dp_not_first = [0] * len(nums)    dp_not_first[0] = 0    dp_not_first[1] = nums[1]    for i in range(2, len(nums)): dp_not_first[i] = max(dp_not_first[i - 2] + nums[i], dp_not_first[i - 1])    # 不偷最后一间    dp_not_last = [0] * len(nums)    dp_not_last[0] = nums[0]    dp_not_last[1] = max(nums[0], nums[1])    for i in range(2, len(nums)-1): dp_not_last[i] = max(dp_not_last[i - 2] + nums[i], dp_not_last[i - 1])    return max(dp_not_first[-1], dp_not_last[-2])

🌈代码注释

def rob(nums):    if len(nums) == 1:   # nums长度为1，只有一家可偷 return nums[0]    # 直接返回nums[0]    # 不偷第一间    dp_not_first = [0] * len(nums)  # 初始化元素为0的dp_not_first数组    dp_not_first[0] = 0    # 因为不偷第一间所以直接将第一间所有金额变为0    dp_not_first[1] = nums[1]     # 初始化dp数组基础    for i in range(2, len(nums)): dp_not_first[i] = max(dp_not_first[i - 2] + nums[i], dp_not_first[i - 1])    # 不偷最后一间    dp_not_last = [0] * len(nums)    dp_not_last[0] = nums[0]# 因为偷第一间所以直接不将第一间所有金额变为0    dp_not_last[1] = max(nums[0], nums[1])    for i in range(2, len(nums)-1):      # 遍历第一间到倒数第二间，不遍历最后一间 dp_not_last[i] = max(dp_not_last[i - 2] + nums[i], dp_not_last[i - 1])    return max(dp_not_first[-1], dp_not_last[-2])  # dp_not_last最后一个元素为0，（因为不遍历到最后一间房子，且[0] * len(nums))所以取dp_not_last[-2]来比较

 🌈优化

从图像演示可以看出，dp[i]数组的判断仅由最新的两个dp[i]结果确定

所以再不同时偷第一和最后一间的基础上我们便可以只记录最新的两个dp[i]结果即可

if len(nums) == 1:     return nums[0] first_status, second_status = 0, 0 for num in nums:     first_status, second_status = second_status, max(first_status + num, second_status) return second_status    return max(compare(nums[:-1]), compare(nums[1:])) if len(nums) !=1 else nums[0]

最后成功获得一幅白金手镯手铐👮‍♂️

今天就到这，明天见。🚀

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄