3. House Robbers

 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.
Answer:

Think of the answer in terms of a decision tree. You can either start at position at index 0 or 1. Since you can't rob the adjacent cell, you have 2 options at each index- you can either jump to index i+2 or i+3 for the most optimal answer. Brute force solution is to draw out the tree, do DFS and find the maximum of all totals.

Brute Force

Dynamic Programming solution:

If you use a 1D array to store the most optimal solution at each index, you'll reduce the time complexity from O(2^n) to O(n).

1.  Create a memoization data structure : 1D Array 'dp'
2.  The first element dp[0] is the first cost
3.  The second element dp[1] is the maximum of first 2 cost elements.

Initialize dp index 0 and 1

      4. The logic is you either "SKIP/ROB" each house.

          The standard recurrence is:

$$dp[i]=\max (dp[i-1],dp[i-2]+cost[i])$$

          This means:

• Either skip the current house (take dp[i-1])

• Or rob it (take cost[i] + dp[i-2])

  

  skip or rob
  

  
  

  5. Return the last element of the dp array 

  

  return the last element