LeetCode 198. 打家劫舍
原创LeetCode 198. 打家劫舍
原创
freesan44
修改于 2021-11-15 08:43:07
修改于 2021-11-15 08:43:07
题目地址(198. 打家劫舍)
https://leetcode-cn.com/problems/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 。提示：
1 <= nums.length <= 100
0 <= numsi <= 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)$
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录