LeetCode 198. House Robber 题解

LeetCode 198. House Robber 题解题目描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。示例 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 。解题思路方法动态规划思路定义dp[i]为前i个房屋能偷窃到的最高金额状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i-1])解释对于第i个房屋有两种选择不偷它此时金额为dp[i-1]或者偷它此时金额为dp[i-2] nums[i-1]初始化dp[0] 0没有房屋时金额为 0dp[1] nums[0]只有一个房屋时只能偷它复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(n)需要一个长度为 n1 的数组来存储状态。方法动态规划空间优化思路观察到dp[i]只依赖于dp[i-1]和dp[i-2]因此可以使用两个变量来存储前两个状态不需要使用数组初始化prev1为0对应dp[0]prev2为0对应dp[-1]遍历数组current max(prev1, prev2 nums[i])prev2 prev1prev1 current复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法动态规划class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * (n 1) dp[0] 0 dp[1] nums[0] for i in range(2, n 1): dp[i] max(dp[i-1], dp[i-2] nums[i-1]) return dp[n]方法动态规划空间优化class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 0: return 0 if n 1: return nums[0] prev1 0 # 对应 dp[i-1] prev2 0 # 对应 dp[i-2] for num in nums: current max(prev1, prev2 num) prev2 prev1 prev1 current return prev1测试用例测试用例 1输入nums [1,2,3,1]输出4测试用例 2输入nums [2,7,9,3,1]输出12测试用例 3输入nums []输出0测试用例 4输入nums [5]输出5总结本题是动态规划的经典问题主要考察对状态定义和状态转移方程的理解。通过动态规划我们可以高效地计算出不触动警报装置的情况下能够偷窃到的最高金额。动态规划的核心思想是通过填充一个一维数组记录前i个房屋能偷窃到的最高金额。对于每个房屋我们有两种选择不偷它或者偷它选择其中金额较大的那个。空间优化的方法通过使用两个变量来存储前两个状态进一步降低了空间复杂度使算法更加高效。这种方法不仅适用于打家劫舍问题还可以应用于许多其他需要动态规划解决的问题例如最大子数组和、最长递增子序列等。掌握动态规划的思想对于解决这类问题非常重要。