geekcomputers / geekcomputers/Python

House Robber and House Robber II Leetcode DP Solution in Python

Open
#1,811 0 comments 0 reactions 0 assignees View on GitHub

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.