Day 2 : 198 House Robber

You're a robber deciding which houses to rob along a street, where each house has a certain amount of money.

To avoid triggering security alarms, you can't rob two adjacent houses; given an array `nums` of house values, calculate the maximum money you can steal without alerting the police.

Before we get started let's take a deep breath…This is a warm-up exercise for the year to come!!!

It took me some good time to wrap my head around this problem, so let’s take it step by step!

• What are we asked? Find the max amount of money we can rob without getting caught! 🤑 

• What do we need to calculate each step? For each step, we need to maximize for gains, does it make more sense to rob 2 houses over? or the house adjecent?

• Base cases: dp[0] = nums[0] dp[1] = max(nums[0], nums[1] 

Let's look at an example with [2,7,9,3,1].

The sequence builds up like this:

1. dp[0] = 2

2. dp[1] = 7

3. dp[2] = cost[2] + max((dp[0]+nums[2]), dp[1])

We will use dynamic programming to solve this problem. This problem is a combination of coin change and climbing stairs. If you need a refresher on dynamic programming.

The key difference is we'll be maximizing profit instead of minimizing cost, and handling the constraint of not robbing adjacent houses. We'll build iteratively from the base cases:

We start by initializing an array dp where dp[i] represents the maximum amount we can rob up to house i. We'll set:

• dp[0] = nums[0] (rob first house)

• dp[1] = max(nums[0], nums[1]) (maximum of first two houses)

Then we build the array up 🏗️, solving one house at a time from 2 up to n. For each house i:

1. We consider both options at house i:

   • Skip this house (take previous best)

   • Rob this house (take best from two houses back + current house)

2. Keep track of the maximum result found

To track the maximum result at each house:

• dp[i] - current best (maximum) amount we can rob up to house i

• dp[i-1] - maximum if we skip current house

• dp[i-2] - maximum if we rob current house (must add nums[i])

• nums[i] - amount in current house

• dp[i-2] + nums[i] - adds current house to best from two back

• max(dp[i-1], dp[i-2] + nums[i]) - keeps maximum between skipping or robbing

This gives us our final DP transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

class Solution {
public:
   
    int rob(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0]; 
        }
        if (nums.size() == 2) {
            return max(nums[0], nums[1]); 
        }
        
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for(int x = 2; x < nums.size(); x++) {
            dp[x] = max(dp[x-2] + nums[x], dp[x-1]);
        }
        return dp[nums.size()-1];   
    }
};

Let me invoke you into my cult

Media worth seeing

1. Bad Bunny regresa a la gente latinaaaaaaaa

2. 3blue1brown is the best Math channel I have found! He just released a LLMs series and it is the best explanation in the internet has of how LLMs work

3. How To Be Hot Smart Rich

Hacks of the week

I truly believe you can gaslight yourself to success.

1. The shorter the time you give yourself to take action the more likely you’ll be successful. I read a tweet on Friday about a guy who was walking a marathon each week and I decided to walk one the very next day (evidence attached!!)

   

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!