LeetCode 198. 打家劫舍
2023-03-14 22:46:45 时间
题目地址(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)$
相关文章
- 免疫沉淀常见问题解答 | MedChemExpress
- JAK-STAT 通路与炎症和自身免疫性疾病 | MedChemExpress
- 阿里云服务器购买和使用须知
- 2023图片文字识别软件ABBYY功能介绍
- 我的ESC使用心得
- 泼辣修图2023免费版和会员功能对比介绍
- 初次使用阿里云服务器心得
- SAP QM Quality Certificate系列2
- ECS简单使用
- Docker 应用实践-镜像篇
- 飞天加速计划·高校学生在家实践使用体验
- 阿里云智能推荐服务端PHP SDK Quick Start
- 复刻画龙产品之新春气泡兔
- 看板:自我管理的高效工具!
- 小白第一次ECS使用体验
- 阿里云服务器购买价格贵吗?一般价格是多少?
- 【Linux操作系统】yum三板斧和yum源的配置
- 每周小结(*91):寻觅意义
- 从决策者的角度理解 DevOps
- 使用 Excel cdata addin 连接 SAP ABAP 系统时遇到错误消息 Unable to connect to SAP system