Python每日一练-----打家劫舍
⛅（day13）
目录
🖍题目：
题目分析：
解题思路：
🌈动态规划解法
🌈代码注释
🌈优化
🖍题目：
假设你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组nums，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。（1 <= nums.length <= 100）
🌠示例 1:
输入：[1,2,3,1]
输出：4
原由：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
🌠示例 2:
输入：[2,7,9,3,1]
输出：12
原由：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
题目分析：
在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.如何初始化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 = [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 - 2] + nums[i], dp[i - 1]) return dp[-1]🌈代码注释
def rob(nums): if len(nums) == 1: # nums长度为1，只有一家可偷 return nums[0] # 直接返回nums[0] dp = [0] * len(nums) # 初始化元素为0的dp数组 dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) # 初始化dp数组基础 for i in range(2, len(nums)): # 因为dp[i-2],为了不超出数组所以i从2开始 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) return dp[-1] # 因为dp[i]数组从左往右记录着盗取的到的最大金额所以dp数组最后一个必然是最大金额数🌈优化
从图像演示可以看出，dp[i]数组的判断仅由最新的两个dp[i]结果确定
所以我们便可以只记录最新的两个dp[i]结果即可
def rob(nums): size = len(nums) if size == 1: return nums[0] first_status, second_status = nums[0], max(nums[0], nums[1]) for i in range(2, size): first_status, second_status = second_status, max(first_status + nums[i], second_status) return second_status最后成功获得一幅白金手镯手铐👮♂️
今天就到这，明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄