forked from shichao-an/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution.py
More file actions
34 lines (30 loc) · 1018 Bytes
/
Copy pathsolution.py
File metadata and controls
34 lines (30 loc) · 1018 Bytes
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
"""
You are a professional robber planning to rob houses along a street. Each
house has a certain amount of money stashed, the only constraint stopping you
from robbing each of them is that adjacent houses have security system
connected and it will automatically contact the police if two adjacent houses
were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each
house, determine the maximum amount of money you can rob tonight without
alerting the police.
"""
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
t = [0 for i in range(n + 1)]
if n == 0:
return t[n]
t[1] = nums[0]
if n <= 1:
return t[n]
t[2] = max(nums[:2])
for i in range(3, n + 1):
t[i] = max(t[i - 2] + nums[i - 1], t[i - 1])
return t[n]
a1 = [4, 1, 6, 10, 5, 13, 2, 7]
s = Solution()
print(s.rob(a1))