[Leetcode] House Robber

198. House Robber

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 numsrepresenting 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 <= 100

0 <= nums[i] <= 400

How to approach?

Recursion with memoization

function rob(nums: number[]): number {
    const memo = new Map<number, number>();

    const robFrom = (i: number, nums: number[]): number => {
        if (i >= nums.length) {
            return 0;
        }

        if (memo.has(i)) {
            return memo.get(i)!;
        }

        const ans = Math.max(
            robFrom(i + 1, nums),
            robFrom(i + 2, nums) + nums[i]
        );

        memo.set(i, ans);
        return ans;
    };

    return robFrom(0, nums);
}

1. create Map to save the key i and value profit.
2. create robFrom function which takes i index of current house and the nums array which represents the money in each house.
3. and lastly return the result of the function from index 0.
4. when the current house index exceeds houses' length, it will return 0, since it's not valid.
5. and it will checked already calculated result in memo Map to get the computated result of the current house index if memo already has it.
6. and create the ans variable to computate the which one will be better choice for maximum profit at current location which is determining two options, rob this current house and skip the next house and go to the i+2 locaiton house or rob next house.
7. get the ans and set it in Map. and return the ans in the function.

summary

using Map to set and get the result of the max profit calculation from the i index. and use it when recursion happened. Think of this robbery happening in current location or skip to the next house by calculation the maximum profit in recursion.

Dynamic Programming

function rob(nums: number[]): number {
    const N = nums.length;

    if (N === 0) return 0;
    if (N === 1) return nums[0];

    const maxRobbedAmount: number[] = new Array(N + 1).fill(0);
    
    maxRobbedAmount[N] = 0; 
    maxRobbedAmount[N - 1] = nums[N - 1]; 

    for (let i = N - 2; i >= 0; i--) {
        maxRobbedAmount[i] = Math.max(
            maxRobbedAmount[i + 1],              
            maxRobbedAmount[i + 2] + nums[i]  
        );
    }
    return maxRobbedAmount[0];
}

1. Create N as nums.length.
2. when N is 0, return 0 there is nothing to rob.
3. when N is 1, rob the one and only house and get max-profit.
4. create an array which has N+1 length. since it's checking the houses from 0 to the Nth house.
5. and set the N index element as 0, since there is no house to rob.
6. and N-1 index element as the last element in nums, since there is only one house left to rob.
7. so the base cases are set, use the for loop starting from N-2, and decrement by one, choose the Math.max between the choices of skip this house(i+1) or rob this current i house and skip the next house(i+2, + nums[i])
8. this will be saved in the array as max profit they can get at i th location house.
9. return the array's 0 index element since it will have the max profit when robber robbed all the houses from 0 to N based on the rule.

summary

create the DP table so robber can save the max profit calculation based on the pre calculated result happening from the right side to the left side.

Optimized Dynamic Programming

function rob(nums: number[]): number {
    const N = nums.length;

    if (N === 0) return 0;
    if (N === 1) return nums[0];

    let robNextPlusOne = 0;
    let robNext = nums[N - 1];

    for (let i = N - 2; i >= 0; i--) {
        let current = Math.max(
            robNext,
            robNextPlusOne + nums[i]
        );
        robNextPlusOne = robNext
        robNext = current
    }
    return robNext
}

1. same approach as dynamic programming but use 2 variables to save the i+1 value and i+2 value and shift the variables in for loop to reused it in next i index.
2. there is no array to save the max profit values from i index.

summary

it's space optimized since there is not array to save the values for caculation but use the 2 variables to compare.