动态规划在Java中的实现：打家劫舍问题

问题描述

打家劫舍问题是一个经典的动态规划问题。假设你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统。如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算在不触动警报装置的情况下，能够偷窃到的最高金额。

动态规划的基本思想

动态规划通过将问题分解为子问题来求解。对于打家劫舍问题，关键在于找到状态转移方程，即如何通过子问题的解来推导出更大规模问题的解。

状态定义与转移方程

定义 dp[i] 为偷窃到第 i 个房屋时能够获得的最大金额。状态转移方程可以表示为：

• 偷窃第 i 个房屋：dp[i] = nums[i] + dp[i-2]
• 不偷窃第 i 个房屋：dp[i] = dp[i-1] 因此，状态转移方程为： [ dp[i] = \max(dp[i-1], nums[i] + dp[i-2]) ]

初始条件

• dp[0] = nums[0]
• dp[1] = \max(nums[0], nums[1])

Java实现代码

public class HouseRobber {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
        }
        return dp[nums.length - 1];
    }
}

空间优化

由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，可以将空间复杂度优化为 (O(1))：

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    if (nums.length == 1) {
        return nums[0];
    }
    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < nums.length; i++) {
        int current = Math.max(prev1, nums[i] + prev2);
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

动态规划打家劫舍变种问题概述

变种问题1：环形房屋（House Robber II）

问题描述：房屋围成一圈，即第一个和最后一个房屋相邻，其他条件不变。

解决方法
将环形问题拆解为两个线性问题：

1. 不抢最后一个房屋，计算 nums[0..n-2] 的最大金额。
2. 不抢第一个房屋，计算 nums[1..n-1] 的最大金额。
   最终结果为两者的最大值。

代码实现

public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    return Math.max(
        robHelper(nums, 0, nums.length - 2),
        robHelper(nums, 1, nums.length - 1)
    );
}

private int robHelper(int[] nums, int start, int end) {
    int prev1 = 0, prev2 = 0;
    for (int i = start; i <= end; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

变种问题2：二叉树房屋（House Robber III）

问题描述：房屋排列为二叉树，不能同时抢劫直接相连的父子节点。

解决方法
使用后序遍历，动态规划结合树形结构：

1. 定义 int[] dfs(TreeNode node)，返回 [抢当前节点的最大值, 不抢当前节点的最大值]。
2. 抢当前节点时，左右子节点不能抢；不抢时，左右子节点可抢或不抢（取最大值）。

代码实现

public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}

private int[] dfs(TreeNode node) {
    if (node == null) return new int[2];
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    int rob = node.val + left[1] + right[1];
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{rob, notRob};
}

变种问题3：间隔k个房屋（House Robber with k-distance）

问题描述：不能抢劫相邻的k个房屋，扩展为间隔k个房屋。

解决方法
使用动态规划数组 dp[i] 表示前i个房屋的最大金额，转移时需检查前k个房屋：
dp[i] = max(dp[i-1], dp[i-k-1] + nums[i])。

代码实现

public int rob(int[] nums, int k) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length + 1];
    dp[1] = nums[0];
    for (int i = 2; i <= nums.length; i++) {
        int prev = (i - k - 1 >= 0) ? dp[i - k - 1] : 0;
        dp[i] = Math.max(dp[i - 1], prev + nums[i - 1]);
    }
    return dp[nums.length];
}

变种问题4：带权值的打家劫舍

问题描述：抢劫房屋有概率被抓住，需最大化期望金额（金额乘以成功概率）。

解决方法
动态规划转移时乘以概率：
dp[i] = max(dp[i-1], dp[i-2] + nums[i] * p[i])。

代码实现

public double robWithProbability(int[] nums, double[] p) {
    double prev1 = 0, prev2 = 0;
    for (int num : nums) {
        double curr = Math.max(prev1, prev2 + num * p[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

打家劫舍变种问题的核心是动态规划，需根据约束条件调整状态转移方程。环形问题拆分为线性，树形问题结合DFS，间隔问题扩展状态检查范围，概率问题引入加权计算。

总结

打家劫舍问题的动态规划解法关键在于定义状态和状态转移方程。不同变体的问题可以通过调整状态定义和初始条件来解决。树形房屋问题需要结合树的后序遍历和动态规划思想。