当前位置：首页 > article >正文

小偷之打家劫舍

article 2025/3/4 5:05:39

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路：

首先设数组 `nums` 存储每间房屋的现金金额，长度为 `n`。定义 `dp[i]` 表示偷窃前 `i` 间房屋所能获得的最高金额。这里的 `i` 取值范围是从 `0` 到 `n`。对于第 `i` 间房屋，有两种选择：偷或者不偷。不偷第 `i` 间房屋：那么能获得的最高金额就等于偷窃前 `i - 1` 间房屋的最高金额，即 `dp[i] = dp[i - 1]`。偷第 `i` 间房屋：由于相邻房屋的防盗系统相连，所以不能偷第 `i - 1` 间房屋，此时能获得的最高金额是偷窃前 `i - 2` 间房屋的最高金额加上第 `i` 间房屋的现金金额，即 `dp[i] = dp[i - 2] + nums[i - 1]`（注意 `nums` 数组下标从 `0` 开始，所以第 `i` 间房屋对应 `nums[i - 1]`）。综合这两种情况，为了使偷窃到的金额最高，需要取这两种选择中的最大值，因此状态转移方程为：
`dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])`当 `i = 0` 时，意味着没有房屋可偷，所以 `dp[0] = 0`。当 `i = 1` 时，只有一间房屋可以偷，那么能获得的最高金额就是这间房屋的现金金额，即 `dp[1] = nums[0]`。通过状态转移方程，从 `i = 2` 开始依次计算 `dp[i]` 的值，直到 `i = n`。最终，`dp[n]` 就是偷窃前 `n` 间房屋所能获得的最高金额。

具体代码;

import java.util.Scanner;

// 解决方案类，用于计算在不触动警报的情况下能偷窃到的最高金额
class Solution198 {
    // 主方法，实现计算最高偷窃金额的逻辑
    public int rob(int[] nums) {
        // 处理数组为空的情况，若数组为空则无法偷窃，返回 0
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 若数组只有一个元素，直接返回该元素的值，即只能偷窃这一个房屋
        if (nums.length == 1) {
            return nums[0];
        }
        // 初始化前两个状态，prev2 表示偷窃到第 0 个房屋时的最高金额
        int prev2 = nums[0];
        // prev1 表示偷窃到第 1 个房屋时的最高金额，取第 0 个和第 1 个房屋金额的最大值
        int prev1 = Math.max(nums[0], nums[1]);

        // 从第 2 个房屋开始遍历数组
        for (int i = 2; i < nums.length; i++) {
            // 当前房屋的最高偷窃金额，取不偷当前房屋（即 prev1）和偷当前房屋（prev2 + nums[i]）的最大值
            int curr = Math.max(prev1, prev2 + nums[i]);
            // 更新 prev2 为 prev1，为下一次循环做准备
            prev2 = prev1;
            // 更新 prev1 为当前房屋的最高偷窃金额
            prev1 = curr;
        }
        // 返回最后一个房屋计算出的最高偷窃金额
        return prev1;
    }
}

// 主类，用于测试 Solution198 类的功能
public class HouseRobber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 提示用户输入房屋金额，元素之间用逗号分隔
        System.out.println("请输入每个房屋存放的金额，元素之间用逗号分隔：");
        String input = scanner.nextLine();
        String[] numStrings = input.split(",");
        int[] nums = new int[numStrings.length];
        for (int i = 0; i < numStrings.length; i++) {
            nums[i] = Integer.parseInt(numStrings[i].trim());
        }

        // 创建 Solution198 类的实例
        Solution198 solution = new Solution198();
        // 调用 rob 方法计算最高偷窃金额
        int result = solution.rob(nums);
        System.out.println("在不触动警报装置的情况下，一夜之内能够偷窃到的最高金额是: " + result);

        scanner.close();
    }
}

运行截图：