House Robber II

描述

This time, all houses at this place are arranged in a circle.

分析

如果抢劫第一家，则不可以抢最后一家；否则，可以抢最后一家。因此，这个问题就转化成为了两趟动规，可以复用 "House Robber" 的代码。

代码

  1. // House Robber II
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public int rob(int[] nums) {
  5.         if (nums.length == 1) return nums[0];
  6.         return Math.max(rob1(nums, 0, nums.length - 1),
  7.                 rob1(nums, 1, nums.length));
  8.     }
  10.     private static int rob1(int[] nums, int begin, int end) {
  11.         if (nums == null || begin >= end) return 0;
  12.         if ((end - begin) == 1) return nums[begin];
  14.         int even = nums[begin];
  15.         int odd = Math.max(nums[begin], nums[begin + 1]);
  17.         for (int i = begin + 2; i < end; ++i) {
  18.             if ((i-begin) % 2 == 0) {
  19.                 even = Math.max(even + nums[i], odd);
  20.             } else {
  21.                 odd = Math.max(odd + nums[i], even);
  22.             }
  23.         }
  24.         return Math.max(even, odd);
  25.     }
  26. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dp/house-robber-ii.html