geekcomputers / geekcomputers/Python
House Robber and House Robber II Leetcode DP Solution in Python
Open
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 35.4k
- Forks
- 12.9k
- Avg merge
- 2h 37m
- Merged PRs (30d)
- 1
Description
I've House Robber and House Robber II solutions in python with comment explanation
**House Robber **
class Solution:
def rob(self, nums: List[int]) -> int:
dp = [0]*len(nums)
# picking up the first house
dp[0] = nums[0]
for i in range(1,len(nums)):
pick = nums[i]
if i>1:
# since second has been picked the robber can add the prev2 as he has not robbed previous house
pick+=dp[i-2]
# since second is house is not picked for robbery so the first house is added
not_pick = 0+dp[i-1]
dp[i] = max(pick,not_pick)
return dp[-1]
House Robber II
class Solution:
def houseRobber(self,a):
prev = a[0]
prev2 = 0
for i in range(1,len(a)):
pick = a[i]
if i>1 :
pick+=prev2
not_pick = 0+prev
prev2 = prev
prev = max(pick,not_pick)
return prev
def rob(self, nums: List[int]) -> int:
# the only difference between house robber and this is that
# the houses are in arrange in circle
# that means first and last cannot be together
first_house = []
last_house = []
if len(nums)==1:
return nums[0]
for i in range(len(nums)):
if i!=0:
last_house.append(nums[i])
if i!=len(nums)-1:
first_house.append(nums[i])
return max(self.houseRobber(first_house),self.houseRobber(last_house))
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by inspecting the repository's existing organization for Leetcode or dynamic-programming examples; the issue does not name a target file or test. Add the two supplied Python solutions with their explanations in the appropriate location, and verify them using the repository's existing validation approach if one is documented.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- content
- Issue type
- Feature
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100