LeetCode: 198. 打家劫舍

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

198. 打家劫舍

LeetCode - 198. 打家劫舍

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

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

示例 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 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

思路分析

假设 f(k) = 从前 k 个房屋中能抢劫到的最大数额，A_i = 第 i 个房屋的钱数。

当 n=1 时，显然 f(1) = A₁。

当 n=2 时，f(2) = max(A₁, A₂)。

当 n=3 时，有两种选项：

将第三个房间金额和第一个房间金额相加；
不算第三个房间，保持当前最大金额。

于是，可以总结出公式: \(f(k)=\max \left(f(k-2)+A_{k}, f(k-1)\right)\)。

剩下的工作就好办了。

让 D瓜哥使用动态规划的模式来重新解读一下：

刻画一个最优解的结构特征：求解抢劫金额最大值。
递归地定义最优解的值： \(f(k)=\max \left(f(k-2)+A_{k}, f(k-1)\right)\)。
计算最优解的值，通常采用自底向上的方法：D瓜哥也按照动态规划（注意表格）的方式来实现，采用自底向上+备忘录的方式来求解，创建一个长度为 n+1 的数组，第 i 个元素表示到第 i 个房间为止，最大抢劫金额；则第 0 个元素为 0，第 1 个元素为 A₁。然后根据上述公式定义，以此类推……
利用计算出的信息构造一个最优解。这一步不需要，暂时忽略。

使用递归、递归+备忘录、自底向上+备忘录，自底向上+简化备忘录四种方式分别实现。

一刷
二刷
三刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber.
 *
 * Memory Usage: 41.2 MB, less than 5.26% of Java online submissions for House Robber.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-23 22:37
 */
public int rob(int[] nums) {
    int k2 = 0;
    int k1 = 0;
    for (int num : nums) {
        int current = Math.max(k2 + num, k1);
        k2 = k1;
        k1 = current;
    }
    return k1;
}

/**
 * Runtime: 1 ms, faster than 5.81% of Java online submissions for House Robber.
 *
 * Memory Usage: 41.9 MB, less than 5.26% of Java online submissions for House Robber.
 */
public int robDP(int[] nums) {
    if (Objects.isNull(nums) || nums.length == 0) {
        return 0;
    }
    int[] memo = new int[nums.length + 1];
    memo[0] = 0;
    memo[1] = nums[0];
    for (int i = 2; i < memo.length; i++) {
        int max = Math.max(memo[i - 2] + nums[i - 1], memo[i - 1]);
        memo[i] = max;
    }
    return memo[nums.length];
}

/**
 * Runtime: 1 ms, faster than 5.81% of Java online submissions for House Robber.
 *
 * Memory Usage: 41.3 MB, less than 5.26% of Java online submissions for House Robber.
 */
public int robRecursionWithMemo(int[] nums) {
    if (Objects.isNull(nums) || nums.length == 0) {
        return 0;
    }
    int[] memo = new int[nums.length];
    Arrays.fill(memo, Integer.MIN_VALUE);
    memo[0] = nums[0];
    rob(nums, memo, nums.length - 1);
    return memo[nums.length - 1];
}

private int rob(int[] nums, int[] memo, int k) {
    if (k == -2 || k == -1) {
        return 0;
    }

    int rob2 = 0;
    if (k - 2 >= 0 && memo[k - 2] >= 0) {
        rob2 = memo[k - 2];
    } else {
        rob2 = rob(nums, memo, k - 2);
    }
    int rob1 = 0;
    if (k - 1 >= 0 && memo[k - 1] >= 0) {
        rob1 = memo[k - 1];
    } else {
        rob1 = rob(nums, memo, k - 1);
    }
    int rob0 = Math.max(rob2 + nums[k], rob1);
    memo[k] = rob0;
    return rob0;
}


// -----
public int robRecursion(int[] nums) {
    return rob(nums, nums.length - 1);
}

private int rob(int[] nums, int k) {
    if (k == -2 || k == -1) {
        return 0;
    }
    return Math.max(rob(nums, k - 2) + nums[k], rob(nums, k - 1));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-23 22:37
 */
public int rob(int[] nums) {
  if (nums.length == 1) {
    return nums[0];
  }
  // 1. 确定 dp 数组（dp table）以及下标的含义
  int[] dp = new int[nums.length];
  // 3. dp 数组如何初始化
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  // 4. 确定遍历顺序
  for (int i = 2; i < nums.length; i++) {
    // 2. 确定递推公式: max(dp[i-3]+nums[i], dp[i-2]+nums[i], dp[i-1])
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[nums.length - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-16 20:19:02
 */
public int rob(int[] nums) {
  if (nums.length == 1) {
    return nums[0];
  }
  if (nums.length == 2) {
    return Math.max(nums[0], nums[1]);
  }
  nums[1] = Math.max(nums[0], nums[1]);
  for (int i = 2; i < nums.length; i++) {
    // dp[i] = max(nums[i] + dp[i-2], dp[i-1])
    nums[i] = Math.max(nums[i - 1], nums[i] + nums[i - 2]);
  }
  return nums[nums.length - 1];
}

LeetCode: 198. 打家劫舍

友情支持

198. 打家劫舍

思路分析

参考资料