Last Updated: 29 Jul, 2020
House Robber
Moderate
Asked in companies
A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.
Input Format :
The first line of input contains a single integer 'N' denoting the total number of houses.
The second line of input contains 'N' single space-separated integers, denoting the amount of money in every 'i-th' house.
Output Format :
The only line of output will print the maximum amount of loot that is possible.
Note :
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
0 <= 'N' <= 10^5
0 <= 'A[i]' <= 10^4
Where 'A[i]' represents the money present in the 'i-th' house.
Time limit: 1 sec
Approaches
Suppose that the robber is at the ith house. The robber has two options:
- If he decides to rob this house, then he cannot rob the next house, so he’ll have to go to the house after that.
- If he decides not to rob this house, he has no restriction over choosing the next house.
You will follow the same for the rest of the houses. Thus, if maxLoot(i) is the maximum loot possible when we’re at the ith house, then the recursive definition follows:
maxLoot(i) = maximum( loot[i] + maxLoot(i+2), maxLoot(i+1))
Note: This approach has an exponential time complexity because this problem has overlapping subproblems for which we recompute the answer over and over again. To avoid that recomputation, we can store the answer of each recursive call (subproblem) in an array or hashmap so that the next time we need the answer to that subproblem, we can directly fetch it from there instead of calculating it again.
We can use dynamic programming to optimize our recursive approach. We store the computed value of maxLoot(i) in a dp array, and we do this for all i between 1 to N. In this way, we can easily obtain back the value when it is required again. Let dp[i] be the maximum value looted after the first i houses, i.e. houses 0 to i - 1.
We can find out how to compute dp[i] from the recurrence relation we found in the recursive approach.
dp[i] = max(dp[i - 1], arr[i - 1] + dp[i - 2])where dp[i] = 0 if i ≤ 0 and arr[i] represents the value of the i'th house (Note: The houses are 0 indexed)
Consider building the result array in a bottom-up fashion (computing the result for smaller to larger numbers of houses). We can observe that if we’re at the ith house, we only require the results for the (i - 1)th and the (i - 2)th houses. Hence, instead of maintaining a whole array, we simply keep track of the last two results obtained.
Similar problems