198. House Robber

Intitution

In the House Robber problem, the challenge is to maximize the amount of money you can steal without robbing two adjacent houses. This forms a classic dynamic programming problem where the decision at each house depends on whether robbing it yields a better total compared to skipping it. The key idea is to make a choice at each step: rob the current house and skip the next, or skip the current house and move to the next one.

Complexity

Space Complexity	Time Complexity
$\text{O}(n)$	$\text{O}(2^n)$

Code

int[] memoizedResults;

public int calculateMaxRobbery(int[] houseMoney, int currentIndex) {
    // Base case: No more houses to rob
    if (currentIndex >= houseMoney.length) return 0;

    // If already computed, return the stored result
    if (memoizedResults[currentIndex] != -1) return memoizedResults[currentIndex];

    // Rob the current house and move to the house after next
    int robThisHouse = houseMoney[currentIndex] + calculateMaxRobbery(houseMoney, currentIndex + 2);

    // Skip the current house and check the next one
    int skipThisHouse = calculateMaxRobbery(houseMoney, currentIndex + 1);

    // Take the maximum of robbing or skipping the current house
    memoizedResults[currentIndex] = Math.max(robThisHouse, skipThisHouse);

    return memoizedResults[currentIndex];
}

public int rob(int[] houseMoney) {
    memoizedResults = new int[houseMoney.length];
    Arrays.fill(memoizedResults, -1); // Initialize memoization array with -1
    return calculateMaxRobbery(houseMoney, 0);
}