Difficulty: Medium
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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
First we can draw a decision tree to understand how to approach this problem better. This is kind of like a brute force approach.
Now we do one step further to analyze the problem. Actually we can break the problem’s each step to 2 choices.
Choice 1: choose to save the 1st number, skip the 2nd number, and worry about all numbers after 2nd number later (as a sub problem)
Choice 2: choose to skip the 1st number, worry about all numbers after 1st number including the 2nd number.
rob = max (arr[o] + rob[2:n], rob[1:n])
basically first one means choice 1 and 2nd means choice two and we have to find out whichever returns max money. This will be our recursion relationship.
To analyze further, we can do this step by step. We can calculate what is the max we can get in each house and then face the choice of either adding the current one or skipping the current one and add the max of all previous houses.
For example, max for the first house is just gonna be 1. max for 2nd house is however, 2, if we choose to [add current and skip previous]. max for 3rd house will be whichever is the max, [old max add current and skip previous] which will turn out to be 4 or [skip current and add previous max] which will turn out to be 2. Of course we want 4. so we put 4 as the max we can get for up to this point. finally we go to house 4. again choices will be simply all previous (max for up to house 3) = 4 or skip previous(house 3) and use old max (house 2) then add current which is 2 + 1 = 3. Apparently 4 is bigger so we will choose 4.
The code for this problem:
All of this is just for my own user. Original author of the video is NeetCode from Youtube.
