House Robber Problem - Dynamic Programming
Table Approach

Problem:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses are arranged in a line, and adjacent houses have security systems connected — it will automatically alert the police if two adjacent houses are broken into on the same night.

Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police.

Example:

Input: nums = [2, 7, 9, 3, 1] nums = [5, 2, 1, 5, 3, 6, 5, 8, 9]

Output: 12

Explanation: Rob house 0 (money = 2), house 2 (money = 9), and house 4 (money = 1).
Total = 2 + 9 + 1 = 12

Dynamic Programming Idea:

We construct a 1D array dp[i] where each cell represents the maximum amount of money that can be robbed up to house i.

Base Case:

Transition Formula:

For each house i (where i ≥ 2), we have two choices:

dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])

This means at each step we decide whether to rob the current house or skip it.

Complexity Analysis:

Time Complexity: O(n)
We iterate through the array once.

Space Complexity: O(n)
We store an array of size n for the DP table.

Example Table:

For nums = [2, 7, 9, 3, 1]

House (i) 0 1 2 3 4
Money 2 7 9 3 1
dp[i] 2 7 11 11 12

Java Implementation:

public class HouseRobber {
    
    public static int rob(int[] nums) {
        int n = nums.length;
        
        // Граничные случаи
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        // Создаем DP таблицу
        int[] dp = new int[n];
        
        // Базовые случаи
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // Заполняем таблицу
        for (int i = 2; i < n; i++) {
            // Максимум из: не грабить текущий дом ИЛИ грабить текущий + максимум от i-2
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        
        return dp[n - 1];
    }
    
    // Метод для печати таблицы DP
    public static void printDPTable(int[] nums, int[] dp) {
        int n = nums.length;
        
        System.out.println("\n" + "=".repeat(60));
        System.out.println("DP Table Visualization");
        System.out.println("=".repeat(60));
        
        // Печать заголовков
        System.out.print("House (i):    ");
        for (int i = 0; i < n; i++) {
            System.out.printf("%5d ", i);
        }
        System.out.println("\n" + "-".repeat(60));
        
        // Печать значений домов
        System.out.print("Money:        ");
        for (int i = 0; i < n; i++) {
            System.out.printf("%5d ", nums[i]);
        }
        System.out.println();
        
        // Печать DP значений
        System.out.print("dp[i]:        ");
        for (int i = 0; i < n; i++) {
            System.out.printf("%5d ", dp[i]);
        }
        System.out.println("\n" + "=".repeat(60));
    }
    
    public static void main(String[] args) {
        // Пример 1
        int[] nums1 = {2, 7, 9, 3, 1};
        System.out.println("Example 1:");
        System.out.println("Houses: " + java.util.Arrays.toString(nums1));
        
        // Получаем DP таблицу для визуализации
        int n = nums1.length;
        int[] dp = new int[n];
        dp[0] = nums1[0];
        dp[1] = Math.max(nums1[0], nums1[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], nums1[i] + dp[i - 2]);
        }
        
        printDPTable(nums1, dp);
        int result1 = rob(nums1);
        System.out.println("Maximum money that can be robbed: " + result1);
        
        // Пример 2
        System.out.println("\n\nExample 2:");
        int[] nums2 = {1, 2, 3, 1};
        System.out.println("Houses: " + java.util.Arrays.toString(nums2));
        
        int[] dp2 = new int[nums2.length];
        dp2[0] = nums2[0];
        dp2[1] = Math.max(nums2[0], nums2[1]);
        for (int i = 2; i < nums2.length; i++) {
            dp2[i] = Math.max(dp2[i - 1], nums2[i] + dp2[i - 2]);
        }
        
        printDPTable(nums2, dp2);
        int result2 = rob(nums2);
        System.out.println("Maximum money that can be robbed: " + result2);
        
        // Пример 3
        System.out.println("\n\nExample 3:");
        int[] nums3 = {5, 3, 4, 11, 2};
        System.out.println("Houses: " + java.util.Arrays.toString(nums3));
        
        int[] dp3 = new int[nums3.length];
        dp3[0] = nums3[0];
        dp3[1] = Math.max(nums3[0], nums3[1]);
        for (int i = 2; i < nums3.length; i++) {
            dp3[i] = Math.max(dp3[i - 1], nums3[i] + dp3[i - 2]);
        }
        
        printDPTable(nums3, dp3);
        int result3 = rob(nums3);
        System.out.println("Maximum money that can be robbed: " + result3);
    }
}

Output Example:

Example 1:
Houses: [2, 7, 9, 3, 1]
============================================================
DP Table Visualization
============================================================
House (i):        0     1     2     3     4 
------------------------------------------------------------
Money:            2     7     9     3     1 
dp[i]:            2     7    11    11    12 
============================================================
Maximum money that can be robbed: 12


Example 2:
Houses: [1, 2, 3, 1]
============================================================
DP Table Visualization
============================================================
House (i):        0     1     2     3 
------------------------------------------------------------
Money:            1     2     3     1 
dp[i]:            1     2     4     4 
============================================================
Maximum money that can be robbed: 4

· Asankanov Erbol 🐦‍⬛ ·