Question
An array that contains the only integer is given as an argument. And sum up the element of value and find the sum of the maximum. However, you can not pick up the element if you chose the adjacent one before. Return the maximum amount of the sum.
Solution
Usually, this kind of problem is supposed to be solved by dynamic programming. They are same as a brute-force-solution with memorization. Dynamic programming works more efficiently than brute-force-solution.
At first, I thought I could solve this by Greedy but I noticed that it is impossible because whether taking the current value depends on the elements that I have not checked yet. If the problem is a greedy problem, we should consider only how I make the most profitable at this time. The previous decision will never change by the current value.
Whether I should take the current value depends on comparing the most profitable value before one step and before two steps. I could lead to the answer when thinking of those two values and the current value.
I defined an array that has a length of two. I store the first value as the maximum sum before two steps. And, the second value is to store the value before one step. The second value is to compare which is max value each step.
Submission
Here is the result.
Runtime: 28 ms, faster than 73.43% of Python3 online submissions for House Robber.
Memory Usage: 13.7 MB, less than 9.09% of Python3 online submissions for House Robber.
Time complexity: O(n)
Space complexity: O(1)
This is one loop and the array that stores the value of the previous step is constant. So, Time complexity is O(1) and space is O(1)
This is my code.
def rob(self, nums: List[int]) -> int:
dp = [0, 0]
for n in nums:
dp[0], dp[1] = dp[1], max(dp[1], dp[0] + n)
return dp[1]
https://github.com/nk18chi/leetcode/blob/master/solutions/house_robber/index.py
