每日算法 — 使用java实现打家劫舍：动态规划状态转移与空间优化

问题描述

打家劫舍是一道经典的动态规划入门题。你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例：

输入: nums = [2, 7, 9, 3, 1]
输出: 12
解释: 偷窃第 1、3、5 间房屋，总金额 = 2 + 9 + 1 = 12

算法思路分析

状态定义

设 dp[i] 表示偷窃前 i 间房屋能获得的最大金额。

状态转移方程

对于第 i 间房屋，有两个选择：
– 偷窃：则不能偷第 i-1 间，最大金额为 dp[i-2] + nums[i]
– 不偷：最大金额保持为 dp[i-1]

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

空间优化

由于 dp[i] 只依赖于前两个状态，可以用两个变量替代整个数组，将空间复杂度降至 O(1)。

Java 完整实现

public class HouseRobber {

    /**
     * 方法一：基础动态规划
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    public int robDP(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        if (n == 1) return nums[0];

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            // 状态转移：偷当前房屋 + 前前家的最大，或不偷当前（继承前一家）
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }

    /**
     * 方法二：空间优化动态规划
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    public int robOptimized(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        if (n == 1) return nums[0];

        int prev2 = nums[0]; // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]

        for (int i = 2; i < n; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    /**
     * 方法三：递归 + 记忆化（自顶向下）
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    public int robMemo(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Integer[] memo = new Integer[nums.length];
        return dfs(nums, 0, memo);
    }

    private int dfs(int[] nums, int index, Integer[] memo) {
        if (index >= nums.length) return 0;
        if (memo[index] != null) return memo[index];

        // 选择1：偷当前房屋，然后跳到 index + 2
        int robCurrent = nums[index] + dfs(nums, index + 2, memo);
        // 选择2：不偷当前房屋，跳到 index + 1
        int skipCurrent = dfs(nums, index + 1, memo);

        memo[index] = Math.max(robCurrent, skipCurrent);
        return memo[index];
    }

    /**
     * 扩展一：房屋围成一圈（首尾相邻）
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    public int robCircular(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);

        // 两种情况：不偷第一家 或 不偷最后一家
        return Math.max(
            robRange(nums, 0, n - 2), // 不偷最后一家
            robRange(nums, 1, n - 1)  // 不偷第一家
        );
    }

    /**
     * 偷窃指定区间 [start, end] 的最大金额
     */
    private int robRange(int[] nums, int start, int end) {
        int prev2 = 0;
        int prev1 = 0;
        for (int i = start; i <= end; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    /**
     * 扩展二：二叉树版打家劫舍（树形DP）
     * 每个节点有偷/不偷两种状态
     */
    public int robTree(TreeNode root) {
        int[] result = dfsTree(root);
        // result[0] = 不偷当前节点的最大值
        // result[1] = 偷当前节点的最大值
        return Math.max(result[0], result[1]);
    }

    private int[] dfsTree(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        int[] left = dfsTree(node.left);
        int[] right = dfsTree(node.right);

        // 不偷当前节点：子节点可偷可不偷，取最大值
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前节点：子节点一定不能偷
        int rob = node.val + left[0] + right[0];

        return new int[]{notRob, rob};
    }

    /**
     * 扩展三：带路径追踪的DP（返回偷窃方案）
     */
    public java.util.List<Integer> robWithPath(int[] nums) {
        if (nums == null || nums.length == 0) return new java.util.ArrayList<>();
        int n = nums.length;

        int[] dp = new int[n];
        boolean[] take = new boolean[n]; // 记录是否偷窃

        if (n >= 1) dp[0] = nums[0];
        if (n >= 2) {
            if (nums[1] > nums[0]) {
                dp[1] = nums[1];
                take[1] = true;
            } else {
                dp[1] = nums[0];
                take[0] = true;
            }
        }

        for (int i = 2; i < n; i++) {
            if (dp[i - 2] + nums[i] > dp[i - 1]) {
                dp[i] = dp[i - 2] + nums[i];
                take[i] = true;
            } else {
                dp[i] = dp[i - 1];
            }
        }

        // 回溯找出偷窃的房屋
        java.util.List<Integer> path = new java.util.ArrayList<>();
        int i = n - 1;
        while (i >= 0) {
            if (take[i]) {
                path.add(i);
                i -= 2;
            } else {
                i--;
            }
        }
        java.util.Collections.reverse(path);
        return path;
    }

    // 二叉树节点定义
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        HouseRobber solution = new HouseRobber();
        int[] nums = {2, 7, 9, 3, 1};

        System.out.println("=== 打家劫舍问题 ===");
        System.out.println("房屋金额: " + java.util.Arrays.toString(nums));
        System.out.println("DP 解法: " + solution.robDP(nums.clone()));
        System.out.println("空间优化: " + solution.robOptimized(nums.clone()));
        System.out.println("记忆化递归: " + solution.robMemo(nums.clone()));

        java.util.List<Integer> path = solution.robWithPath(nums.clone());
        System.out.println("偷窃方案 (房屋索引): " + path);
        int sum = 0;
        for (int idx : path) sum += nums[idx];
        System.out.println("方案总金额验证: " + sum);

        // 环形房屋测试
        int[] circular = {1, 2, 3, 1};
        System.out.println("\n环形房屋 " + java.util.Arrays.toString(circular) +
                           " -> 最大金额: " + solution.robCircular(circular));

        // 二叉树测试
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        System.out.println("二叉树版最大金额: " + solution.robTree(root));
    }
}

复杂度分析

扩展思考

1. 间隔至少两间：要求偷窃的房屋之间至少间隔两间，状态转移方程变为 dp[i] = max(dp[i-1], dp[i-3] + nums[i])。
2. 加权图版本：将房屋看作图的节点，边表示相邻关系，转化为最大权独立集问题。
3. 概率版本：每间房屋有被抓的概率，目标是最大化期望收益。

总结

打家劫舍问题以生动的场景揭示了动态规划的本质：每个阶段的决策依赖于之前阶段的最优结果。从线性数组到环形数组，再到二叉树结构，问题逐步升级，展示了状态设计在不同数据结构上的灵活应用。空间优化技巧（滚动数组）是动态规划中降低空间开销的常用手段，值得深入掌握。