Skip to content

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);
}

Comments