卖萌的弱渣

I am stupid, I am hungry.

House Robber 2

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.

Solution

  • Java: 不用dp
(House-Robber2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(nums.length==1)
           return nums[0];
        return Math.max(rob_helper(nums, 0, n-2), rob_helper(nums, 1, n-1));
    }

    public int rob_helper(int[] nums, int lo, int hi){
        int include = 0;
        int exclude = 0;
        for(int j=lo; j<=hi; j++){
            int i = include; int e = exclude;
            include = nums[j]+e;
            // 为什么不是exclude = i: [1,3,1,3,100]
            exclude = Math.max(e,i);
        }
        return Math.max(include,exclude);
    }
}
  • Python: Consider two cases: nums[0] not used and nums[n-1] not used
(House-Robber2.py) download
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

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        n = len(nums)
        dp = [0]*(n)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0],nums[1])

        # case1: dont use dp[0]
        dp[0] = 0
        dp[1] = nums[1]

        for i in range(2,n):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        ans = dp[n-1]

        # case2: don't use dp[n-1]
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])

        for i in range(2,n-1):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])

        return max(ans,dp[n-2])