LeetCode 213. House Robber II
The trick is to find the max value between robbing 0 to n-2 and 1 to n-1, so that we avoid the rounding issue.
public class Solution { public int Rob(int[] nums) { int len = nums.Length; if(nums.Length == 0) return 0; if(nums.Length == 1) return nums[0]; if(nums.Length == 2) return Math.Max(nums[0], nums[1]); int[] h = new int[nums.Length]; h[0] = nums[0]; h[1] = nums[1]; for(int i = 2; i < nums.Length-1; i++){ int max = int.MinValue; for(int j = 0; j < i - 1; j++){ max = Math.Max(nums[i] + h[j], max); } h[i] = max; } int h1 = Math.Max(h[len-2], h[len-3]); h[1] = nums[1]; h[2] = nums[2]; for(int i = 3; i < nums.Length; i++){ int max = int.MinValue; for(int j = 1; j < i - 1; j++){ max = Math.Max(nums[i] + h[j], max); } h[i] = max; } int h2 = Math.Max(h[len-1], h[len-2]); return Math.Max(h1, h2); } }