01-House-Robber.md

House Robber

Problem Link

https://leetcode.com/problems/house-robber/

---

Pattern

• 1D DP

---

Approach

At each house, choose between robbing it plus the best up to two houses back or skipping it.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int take = prev2 + num;
            int skip = prev1;
            int current = Math.max(take, skip);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}