198. House Robber

打家劫舍

问题链接

• 英文网站：198. House Robber

• 中文网站：198. 打家劫舍

问题描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 400

解题思路

本题可以采用动态规划来解决，我们用$nums_i$表示第 i 户人家所拥有的钱数， $dp_i$ 表示该小偷在前 i 户人家，能够偷到的最大总钱数。假设当这个小偷来到第 i+1 户人家的门前时，已经知道了前面 $dp_0\sim dp_i$ 的取值，由于他不能连续偷相邻的两户人家，所以如果他偷了第 i+1 户人家，就不能偷第 i 户人家，那么他此时的总收入应该是 $dp{i-1}+nums{i+1}$ ，我们将这个数记为 t。如果 $t>dp_i$ ，那么 $dp_{i+1}=t$ ，如果 $t\le dp_i$ ，那么他还不如不偷第 i+1 户人家，维持在前 i 户人家得到的收入，也就是 $dp_i$ ，这种情况下， $dp_{i+1}=dp_i$ 。所以， $dp_{i+1}$ 的取值取决于 t 和 $dp_i$ 的大小，即： $dp_{i+1}=max\{dp_i, dp_{i-1}+nums_{i+1}\}$ ，对这个式子做一下变形，可以得到 ：

$$dp_i=max\{dp_{i-1}, dp_{i-2}+nums_i\}$$

这就是状态转移方程。根据状态转移方程，很容易就可以写出代码。

public int rob(int[] nums) {
    int len = nums.length;
    int[] dp = new int[len];
    dp[0] = nums[0];
    for (int i = 1; i < len; i++) {
        if (i == 1) {
            // 前两个数特殊处理
            dp[i] = Math.max(dp[i-1], nums[i]);
        } else {
            dp[i] = Math.max(dp[i-1], nums[i] + dp[i - 2]);
        }
    }
    return dp[len - 1];
}

这段代码的时间复杂度是 O(n)，空间复杂度也是 O(n)。

通过上面这段代码，可以发现，其实我们只要维护dp[i]、dp[i-1] 以及 dp[i-2] 这三个数就可以了，没必要维护一个数组，因为我们只关心小偷分别在当前人家、上一户人家以及上上户人家的最大总收入，所以上面这段代码可以优化成下面这样：

public int rob(int[] nums) {
    int len = nums.length;
    int prePre = 0, pre = nums[0], current = nums[0];
    for (int i = 1; i < len; i++) {
        current = Math.max(pre, prePre + nums[i]);
        prePre = pre;
        pre = current;
    }
    return current;
}

经过优化，我们的代码空间复杂度变成了 O(1)。

相关题目

数组、动态规划

发布时间：2021年7月4日