package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/house-robber-ii/
 */
public class Problem213 {
    public int rob(int[] nums) {
        int max = 0;
        if (nums.length == 1) {
            return nums[nums.length - 1];
        }
        for (int i = 0; i < nums.length - 1; i++) {
            Map<Integer, Value> memo = new HashMap<>();
            Value a = rob(nums, i, memo);
            Value b = rob(nums, i + 1, memo);
            int tmpMax = Math.max(a.value0, b.value1);
            max = Math.max(max, tmpMax);
        }
        return max;
    }

    private static class Value {
        int value0;
        int value1;
    }

    private Value rob(int[] nums, int idx, Map<Integer, Value> memo) {
        if (memo.containsKey(idx)) {
            return memo.get(idx);
        }
        if (idx == nums.length - 1) {
            Value value = new Value();
            value.value0 = 0;
            value.value1 = nums[idx];
            return value;
        }
        if (idx >= nums.length) {
            return new Value();
        }
        Value a = rob(nums, idx + 2, memo);
        Value b = rob(nums, idx + 3, memo);
        int val = nums[idx];
        int max0 = Math.max(a.value0 + val, b.value0 + val);
        int max1 = Math.max(a.value1 + val, b.value1 + val);
        Value value = new Value();
        value.value0 = max0;
        value.value1 = max1;
        memo.put(idx, value);
        return value;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -141,19 +141,22 @@
     int 
-max
+answer
  = 0;%0A  
@@ -301,35 +301,25 @@
         
-Map%3C
 Integer
-, Value%3E
+%5B%5D
  memo = 
@@ -326,19 +326,28 @@
 new 
-HashMap%3C%3E()
+Integer%5Bnums.length%5D
 ;%0A  
@@ -348,37 +348,35 @@
 h%5D;%0A            
-Value
+int
  a = rob(nums, i
@@ -373,16 +373,22 @@
 ob(nums,
+ true,
  i, memo
@@ -406,94 +406,89 @@
     
-Value b = rob(nums, i + 1, memo);%0A            int tmpMax = Math.max(a.value0, b.value1
+memo = new Integer%5Bnums.length%5D;%0A            int b = rob(nums, false, i + 1, memo
 );%0A 
@@ -498,19 +498,22 @@
         
-max
+answer
  = Math.
@@ -520,19 +520,30 @@
 max(
-max, tmpMax
+answer, Math.max(a, b)
 );%0A 
@@ -566,19 +566,22 @@
  return 
-max
+answer
 ;%0A    %7D%0A
@@ -604,101 +604,41 @@
 tic 
-class Value %7B%0A        int value0;%0A        int value1;%0A    %7D%0A%0A    private Value rob(int%5B%5D nums
+int rob(int%5B%5D nums, boolean first
 , in
@@ -648,27 +648,17 @@
 dx, 
-Map%3C
 Integer
-, Value%3E
+%5B%5D
  mem
@@ -678,221 +678,98 @@
 if (
-memo.containsKey(idx)) %7B%0A            return memo.get(idx);%0A        %7D%0A        if (idx == nums.length - 1) %7B%0A            Value value = new Value();%0A            value.value0 = 0;%0A            value.value1 = nums%5Bidx%5D;
+idx == nums.length - 1) %7B%0A            if (first) %7B%0A                return 0;%0A            %7D
 %0A   
@@ -780,29 +780,33 @@
      return 
-value
+nums%5Bidx%5D
 ;%0A        %7D%0A
@@ -858,27 +858,17 @@
  return 
-new Value()
+0
 ;%0A      
@@ -883,87 +883,72 @@
     
-Value a = rob(nums, idx + 2, memo);%0A        Value b = rob(nums, idx + 3, memo);
+if (memo%5Bidx%5D != null) %7B%0A            return memo%5Bidx%5D;%0A        %7D
 %0A   
@@ -956,19 +956,22 @@
     int 
-val
+answer
  = nums%5B
@@ -992,239 +992,154 @@
 int 
-max0 = Math.max(a.value0 + val, b.value0 + val);%0A        int max1 = Math.max(a.value1 + val, b.value1 + val);%0A        Value value = new Value();%0A        value.value0 = max0;%0A        value.value1 = max1;%0A        memo.put(idx, value)
+a = rob(nums, first, idx + 2, memo);%0A        int b = rob(nums, first, idx + 3, memo);%0A        answer += Math.max(a, b);%0A        memo%5Bidx%5D = answer
 ;%0A  
@@ -1155,13 +1155,14 @@
 urn 
-value
+answer
 ;%0A  

Update problem 213