LeetCode 198. House Robber

[Woodyiiiiiii]

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [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: [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.

---

简单的线性DP问题。我的思路是创建一个一维dp数组，dp[i]表示如果要抢劫第i个房子，此时抢夺的最大金钱数是多少。转移状态函数是dp[i] = Math.max(dp[i], dp[j] + nums[i])。(j < i)

class Solution {
    public int rob(int[] nums) {
        int sum = 0, len = nums.length;
        if (len <= 0) return 0;
        else if (len == 1) return nums[0];
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = nums[1];
        for (int i = 2; i < len; ++i)
            for (int j = i - 2; j >= 0; --j) 
                dp[i] = Math.max(dp[i], dp[j] + nums[i]);
        return Math.max(dp[len - 1], dp[len - 2]);
    }
}

然而这样的空间复杂度是O(n)，但时间复杂度变为了平方级别(感觉这跟我之前做的线性DP犯的小问题一致)。我们可以换个角度去理解，dp[i]表示0~i的最大抢劫数，dp[i]可以分为抢劫第i个房子状态和不抢劫第i个房子状态，那么转移函数就是dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。

class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1) return nums.length == 0 ? 0 : 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(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

继续优化，减少空间复杂度：只使用两个变量就可以分别保存前一个值(dp[i - 1])和前两个值dp[i - 2]。

class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1) return nums.length == 0 ? 0 : nums[0];
        int ppre = nums[0], pre = nums[0] > nums[1] ? nums[0] : nums[1];
        for (int i = 2; i < nums.length; ++i) {
            int n = Math.max(ppre + nums[i], pre);
            ppre = pre;
            pre = n;
        }
        return pre;
    }
}

时隔两年后又重新做了这道题。

关键在于：
如何判断下一轮的ppreMax。

解法如下：(ppreMax表示不包括nums[i]的之前的和的最大值，preMax表示包括nums[i]的之前的和最大值)

class Solution {
    public int rob(int[] nums) {
        int ppreMax = 0;
        int preMax = nums[0];
        int max = preMax;
        
        for (int i = 1; i < nums.length; ++i) {
            int tmp = Math.max(ppreMax, preMax);   // most important
            ppreMax += nums[i];
            max = Math.max(ppreMax, preMax);
            
            // calculate preMax and ppreMax
            int t = ppreMax;
            ppreMax = tmp;
            preMax = t;
        }
        
        return max;
    }
}

---

参考资料:

• https://leetcode.com/problems/house-robber/
• [LeetCode] 198. House Robber grandyang/leetcode#198