网络异常，图片无法展示
|
题目地址(198. 打家劫舍)
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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 。
提示：
1 <= nums.length <= 100 0 <= nums[i] <= 400
思路
DP规划，通过判断前一个和前两个最大值，来判断当前偷不偷，并输出最后两个结果，可以进行常量约简，但思路不太清晰，就不写了
代码
- 语言支持：Python3
Python3 Code:
class Solution: def rob(self, nums: List[int]) -> int: length = len(nums) dp = [0]*length dp[0] = nums[0] if length <= 1:return dp[-1] dp[1] = max(dp[0],nums[1]) for i in range(2,length): val = nums[i] dp[i] = max(dp[i-1],dp[i-2]+val) # print(dp) return max(dp[-1],dp[-2]) if __name__ == '__main__': nums = [1,2,3,1] # nums = [2,1] nums = [2,1,1,2] res = Solution().rob(nums) print(res)
复杂度分析
令 n 为数组长度。
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
