当前位置:网站首页>LeetCode#198. raid homes and plunder houses
LeetCode#198. raid homes and plunder houses
2022-07-06 15:21:00 【Rufeng ZHHH】
subject (LeetCode):
You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .
Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .
Example 1:
Input :[1,2,3,1]
Output :4
explain : Steal 1 House No ( amount of money = 1) , And then steal 3 House No ( amount of money = 3).
Maximum amount stolen = 1 + 3 = 4 .
Example 2:
Input :[2,7,9,3,1]
Output :12
explain : Steal 1 House No ( amount of money = 2), Steal 3 House No ( amount of money = 9), Then steal 5 House No ( amount of money = 1).
Maximum amount stolen = 2 + 9 + 1 = 12 .
The practice of this problem is dynamic programming , We can compare LeetCode#53. Maximum subarray and _ As the wind Zhhh The blog of -CSDN Blog
How to do it , You will find that they have many similarities , We also use dp[i] Before presentation i The maximum value obtained by item .
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)==1: # List the special situations first ①
return nums[0]
elif len(nums)==2: # A special case ②
return max(nums)
dp=[0]*len(nums) # When len(nums)>2 when
dp[0]=nums[0] # If only 1 home , Get the value of the first house
dp[1]=max(nums[0],nums[1]) # The first two get the maximum of them
for i in range(2,len(nums)):
dp[i]=max(dp[i-1],dp[i-2]+nums[i]) # If the first i Home theft , Before getting i-1 Home maximum
return dp[len(nums)-1] # If the first i Home does not steal , Before getting i-2 Home maximum and number i Home value
边栏推荐
- 如何成为一个好的软件测试员?绝大多数人都不知道的秘密
- ucore lab7
- Mysql database (I)
- Servlet
- MySQL transactions
- Leetcode simple question: check whether two strings are almost equal
- ucore lab1 系统软件启动过程 实验报告
- Dlib detects blink times based on video stream
- Emqtt distribution cluster and node bridge construction
- How to solve the poor sound quality of Vos?
猜你喜欢
ucore lab8 文件系统 实验报告
C4D quick start tutorial - creating models
CSAPP shell lab experiment report
ucore lab6 调度器 实验报告
What are the commonly used SQL statements in software testing?
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
Heap, stack, queue
Threads and thread pools
Future trend and planning of software testing industry
Brief introduction to libevent
随机推荐
Investment operation steps
Interface test interview questions and reference answers, easy to grasp the interviewer
ucore lab6 调度器 实验报告
CSAPP Shell Lab 实验报告
51 lines of code, self-made TX to MySQL software!
Word macro operation: convert the automatic number in the document into editable text type
Global and Chinese market of barrier thin film flexible electronics 2022-2028: Research Report on technology, participants, trends, market size and share
Cadence physical library lef file syntax learning [continuous update]
Want to change jobs? Do you know the seven skills you need to master in the interview software test
几款开源自动化测试框架优缺点对比你知道吗?
The wechat red envelope cover designed by the object is free! 16888
Should wildcard import be avoided- Should wildcard import be avoided?
如何成为一个好的软件测试员?绝大多数人都不知道的秘密
pytest
Pedestrian re identification (Reid) - data set description market-1501
ucore lab8 文件系统 实验报告
Do you know the advantages and disadvantages of several open source automated testing frameworks?
Build your own application based on Google's open source tensorflow object detection API video object recognition system (II)
In Oracle, start with connect by prior recursive query is used to query multi-level subordinate employees.
MySQL development - advanced query - take a good look at how it suits you