213. House Robber II

发表于 | 分类于

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.

解法1：

两次dp, 每次只考虑头或者尾之中的一个, i.e. [0, n - 1]或者[1, n].
然后找出对应的最大的值就可以了
C++

1

Java

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
public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];    // forward looking
        int res = dp[0];
        for (int i = 1; i < nums.length - 1; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + (i >= 2 ? dp[i - 2] : 0));
            res = Math.max(dp[i], res);
        }
        // backward looking
        dp = new int[nums.length];
        dp[nums.length - 1] = nums[nums.length - 1];
        res = Math.max(res, dp[nums.length - 1]);
        for (int i = nums.length - 2; i > 0; i--) {
            dp[i] = Math.max(dp[i + 1], nums[i] + (i < nums.length - 2 ? dp[i + 2] : 0));
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}