本文共 1068 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到一种方法，能够在一夜内偷窃到的最高金额，而不触动相邻房屋的警报系统。

方法思路

这个问题类似于经典的动态规划问题，可以使用动态规划的方法来解决。我们可以定义一个数组 dp，其中 dp[i] 表示到第 i 个房屋时能够偷到的最多金额。状态转移方程如下：

• 如果我们不偷第 i 个房屋，那么 dp[i] 就等于 dp[i-1]。
• 如果我们偷第 i 个房屋，那么我们不能偷第 i-1 个房屋，这时 dp[i] 等于 dp[i-2] 加上当前房屋的金额。

状态转移方程可以表示为：[ dp[i] = \max(dp[i-1], dp[i-2] + nums[i]) ]

初始化时：

• 当数组长度为 1 时，只能偷第一个房屋，即 dp[0] = nums[0]。
• 当数组长度为 2 时，只能选择偷前两栋房子的其中一栋，取较大的那个。

解决代码

class Solution {    public int rob(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(n)，适用于题目给定的约束条件。

转载地址：http://frgyk.baihongyu.com/