FilesExpand file tree

main

/

0198-house-robber.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (26 loc) · 1.31 KB

main

/

0198-house-robber.py

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (26 loc) · 1.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

"""

Problem: LeetCode 198 - House Robber

Key Idea:

The key idea to solve this problem is to use dynamic programming. We create a list `dp` where `dp[i]` represents the maximum amount of money that can be robbed up to the `i-th` house.

To populate `dp`, we iterate through the houses from left to right. For each house `i`, we have two choices:

1. Rob the current house, which means we add the money from the current house (`nums[i]`) to the amount robbed from two houses before (`dp[i-2]`).

2. Skip the current house and take the maximum amount robbed from the previous house (`dp[i-1]`).

We choose the maximum of these two options and update `dp[i]` accordingly. Finally, `dp[-1]` will contain the maximum amount that can be robbed.

Time Complexity:

The time complexity is O(n) because we iterate through the list of houses once.

Space Complexity:

The space complexity is O(n) because we use a list `dp` to store the maximum amounts that can be robbed up to each house.

"""

class Solution:

def rob(self, nums: List[int]) -> int:

n = len(nums)

if n == 0:

return 0

if n == 1:

return nums[0]

dp = [0] * n

dp[0] = nums[0]

dp[1] = max(nums[0], nums[1])

for i in range(2, n):

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

return dp[-1]