# Number of Distinct Islands 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:** ```plaintext 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:** ```plaintext 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. ``` Below is a **step-by-step** **Dynamic Programming** breakdown for the classic [**House Robber**](https://leetcode.com/problems/house-robber/) problem (LeetCode #198). We’ll follow your six-step approach: --- ## 1️⃣ Problem Explanation (in Simple Words) You are given a list (array) of non-negative integers where each integer represents the amount of money stashed in a house along a street. **You cannot rob two adjacent houses** (to avoid triggering alarms). Your goal is to **maximize** the total amount of money robbed. * **Input:** An array of integers `nums`, e.g., `[2, 7, 9, 3, 1]`. * **Output:** A single integer (the maximum amount of money you can rob without ever robbing two adjacent houses). ### Example **Example:** `nums = [2, 7, 9, 3, 1]` * If you rob house 1 (`2$`), you cannot rob house 2 (`7$`), but you can consider house 3, and so on. * One optimal solution is to rob houses with `7$` + `9$` + `1$` = `17$`. * No two of these robbed houses are next to each other. --- ## 2️⃣ Draw the Decision Tree (to Visualize the Recursion) To understand the recursive calls, let’s label the houses by index: `0, 1, 2, 3, 4`. We define a function `rob(i)` = **maximum amount of money you can rob** from houses in the range `[i .. end]`. At each house i, you have two choices: 1. **Rob house i**: then you **skip house i+1** and continue from house i+2. 2. **Don’t rob house i**: then you move on to house i+1. Decision tree for `nums = [2, 7, 9, 3, 1]`: ```plaintext rob(0) / \ Rob house 0 (2) Skip house 0 (0) / \ rob(2) rob(1) / \ / \ rob(2)+rob(4) ... rob(1)+rob(3) ... (and so on...) ``` * **If we rob house 0 (amount = 2)** → our next decision is at `rob(2)`. * **If we skip house 0** → we continue with `rob(1)`. Eventually, the recursion explores all valid ways to rob houses without adjacency conflict. We pick the maximum sum among all these paths. --- ## 3️⃣ Recursion + Memoization (Top-Down Approach) ### Key Idea 1. **Recursive Function**: Let `robRec(i)` be the maximum amount we can rob from houses starting at index `i`. 2. **Choices**: * **rob house i** → gain `nums[i]` + move to `i+2` (because house `i+1` is off-limits if we rob house `i`). * **skip house i** → just move to `i+1`. 3. **Base Cases**: * If `i >= nums.length`, no houses left → return `0`. 4. **Memoization**: We store results in a cache (e.g., `memo[i]`) to avoid repeated calculations. ### JavaScript Code (Top-Down DP) ```js /** * Rob houses using recursion + memoization. * @param {number[]} nums * @return {number} Max amount of money that can be robbed. */ function rob(nums) { const n = nums.length; const memo = new Array(n).fill(-1); function robRec(i) { // Base case: no houses left to consider if (i >= n) return 0; // If already computed, return from memo if (memo[i] !== -1) { return memo[i]; } // Option 1: Rob this house const robCurrent = nums[i] + robRec(i + 2); // Option 2: Skip this house const skipCurrent = robRec(i + 1); // Take the max memo[i] = Math.max(robCurrent, skipCurrent); return memo[i]; } // Compute starting from house 0 return robRec(0); } // Test console.log(rob([2, 7, 9, 3, 1])); // 12 -> Explanation: 7 + 3 + 2 or 2 + 9 + 1, etc. Actually the best is 2+9+1=12 or 7+3+? Let's see // House 0: 2, skip 1, then rob 2: 9 => total 11, skip 3 or rob 3? Let's see carefully: // Actually let's do a quick check: The best combination is 2 + 9 + 1 = 12, or 7 + 3 = 10, or 7 + 3 + 1 is not possible because 3 and 1 are adjacent to 7 if we skip only 2? Wait, we skip house 2 if we rob house 1. // So the maximum is indeed 12. ``` > **Note on example**: Depending on the array, the maximum can vary. For `[2, 7, 9, 3, 1]`, the best is `2 + 9 + 1 = 12`. Another approach might yield the same or different sum, but **12** is the maximum. --- ## 4️⃣ Tabulation (Bottom-Up Approach) Instead of top-down recursion, we can fill a **dp array** iteratively: 1. **dp\[i\]** = the maximum amount of money that can be robbed from house `i` onward. 2. **Transition**: dp\[i\]=max⁡(nums\[i\]+dp\[i+2\],dp\[i+1\]) * **rob house i** + whatever you get from `i+2` * **skip house i** and look at `dp[i+1]` 3. We want **dp\[0\]** in the end. 4. We fill **dp** from the **right to left**: * Because `dp[i]` depends on `dp[i+1]` and `dp[i+2]`. ### Bottom-Up DP JavaScript ```js /** * Rob houses using bottom-up tabulation. * @param {number[]} nums * @return {number} Max amount of money that can be robbed. */ function robTab(nums) { const n = nums.length; if (n === 0) return 0; // dp[i] = max amount that can be robbed from i..end const dp = new Array(n + 2).fill(0); // We add 2 extra slots to safely handle dp[i+2] without out-of-bounds // Fill from right to left for (let i = n - 1; i >= 0; i--) { // Rob i OR skip i dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]); } // The result is the max amount from house 0 return dp[0]; } // Test console.log(robTab([2, 7, 9, 3, 1])); // 12 ``` --- ## 5️⃣ Optimize Space Complexity (If Possible) In the **tabulation** solution, note that to compute `dp[i]`, we only need **dp\[i+1\]** and **dp\[i+2\]**. So we don’t need the entire `dp`array. ### Space-Optimized Bottom-Up Approach We can use just two variables to store `dp[i+1]` and `dp[i+2]` while iterating: ```js /** * Space-optimized version of robTab. */ function robTabOptimized(nums) { let robNext = 0; // dp[i+1] let robNextNext = 0; // dp[i+2] // Iterate from right to left for (let i = nums.length - 1; i >= 0; i--) { const current = Math.max(nums[i] + robNextNext, robNext); // Shift robNextNext = robNext; robNext = current; } return robNext; // This is dp[0] at the end } // Test console.log(robTabOptimized([2, 7, 9, 3, 1])); // 12 ``` Here: * `robNext` represents `dp[i+1]` (the maximum loot starting from house `i+1`). * `robNextNext` represents `dp[i+2]`. * Each iteration calculates `dp[i]`, which we store in `current`. Then we shift the values accordingly. This reduces our space usage from **O(n)** to **O(1)**, ignoring the input array. --- ## 6️⃣ Time Complexity Analysis 1. **Recursion + Memoization** * We have `n` houses, and we define `robRec(i)` for each `i`. * **Number of states:** `n`. * Each state does **O(1)** work to combine results from `robRec(i+1)` or `robRec(i+2)`. * So the DP approach is **O(n)** in time once memoized. 2. **Tabulation (Bottom-Up)** * We fill `dp` array from `n-1` down to `0`, and each step is **O(1)**. * Overall **O(n)** time. 3. **Space Optimization** * Tabulation can be done in **O(1)** space (beyond the input) using the two-variable method. * The time complexity remains **O(n)**. --- ## Summary The **House Robber** problem is a classic demonstration of **DP** where we decide for each house: **rob it** (and skip the next one) or **skip it** (and proceed to the next). We saw: 1. **Recursive Explanation + Decision Tree** 2. **Top-Down Memoized Code** 3. **Bottom-Up Tabulation Code** 4. **Space Optimization** (down to constant space) 5. **Time Complexity** of **O(n)** in all approaches. With these clear steps, you’ll easily handle variations like **House Robber II** (circular street) and **Delete and Earn**(another spin on the same logic). **Congrats** on another DP problem tackled! Keep up the great work.