package leetcode;

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

/**
 * https://leetcode.com/problems/house-robber/
 */
public class Problem198 {
    public int rob(int[] num) {
        Map<Integer, Integer> memo = new HashMap<>();
        int max1 = rob(num, 0, memo);
        int max2 = rob(num, 1, memo);
        if (max1 > max2) {
            return max1;
        }
        return max2;
    }

    private int rob(int[] num, int idx, Map<Integer, Integer> memo) {
        if (memo.containsKey(idx)) {
            return memo.get(idx);
        }
        if (idx == num.length - 1) {
            return num[idx];
        }
        if (idx >= num.length) {
            return 0;
        }
        int m1 = rob(num, idx + 2, memo);
        int m2 = rob(num, idx + 3, memo);
        int val = num[idx];
        if (m1 > m2) {
            memo.put(idx, val + m1);
            return val + m1;
        }
        memo.put(idx, val + m2);
        return val + m2;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -133,37 +133,27 @@
         
-Map%3C
 Integer
-, Integer%3E
+%5B%5D%5B%5D
  memo = 
@@ -160,19 +160,30 @@
 new 
-HashMap%3C%3E()
+Integer%5Bnum.length%5D%5B2%5D
 ;%0A  
@@ -192,20 +192,17 @@
     int 
-max1
+a
  = rob(n
@@ -207,16 +207,22 @@
 (num, 0,
+ true,
  memo);%0A
@@ -233,20 +233,17 @@
     int 
-max2
+b
  = rob(n
@@ -246,17 +246,24 @@
 ob(num, 
-1
+0, false
 , memo);
@@ -275,81 +275,29 @@
     
-if (max1 %3E max2) %7B%0A            return max1;%0A        %7D%0A        return max2
+return Math.max(a, b)
 ;%0A  
@@ -313,16 +313,23 @@
 private 
+static 
 int rob(
@@ -348,23 +348,25 @@
 nt i
-dx, Map%3CInteger
+ndex, boolean rob
 , In
@@ -370,17 +370,20 @@
  Integer
-%3E
+%5B%5D%5B%5D
  memo) %7B
@@ -399,29 +399,27 @@
 if (
-memo.containsKey(idx)
+index == num.length
 ) %7B%0A
@@ -441,21 +441,9 @@
 urn 
-memo.get(idx)
+0
 ;%0A  
@@ -466,59 +466,86 @@
 if (
-idx == num.length - 1) %7B%0A            return num%5Bidx
+memo%5Bindex%5D%5Brob ? 1 : 0%5D != null) %7B%0A            return memo%5Bindex%5D%5Brob ? 1 : 0
 %5D;%0A 
@@ -566,53 +566,38 @@
    i
-f (id
+nt ma
 x 
-%3E
 = 
-num.length) %7B%0A            return 0;
+0;%0A        if (rob) %7B
 %0A   
@@ -605,26 +605,31 @@
     
-%7D%0A
     
-    int m1 =
+max = Math.max(max,
  rob
@@ -639,23 +639,67 @@
 m, i
-d
+nde
 x + 
-2, memo);%0A
+1, false, memo) + num%5Bindex%5D);%0A        %7D else %7B%0A    
     
@@ -706,18 +706,17 @@
     int 
-m2
+a
  = rob(n
@@ -724,14 +724,22 @@
 m, i
-d
+nde
 x + 
-3
+1, true
 , me
@@ -755,158 +755,151 @@
     
-int val = num%5Bidx%5D;%0A        if (m1 %3E m2) %7B%0A            memo.put(idx, val + m1);%0A            return val + m1;%0A        %7D%0A        memo.put(idx, val + m2)
+    int b = rob(num, index + 1, false, memo);%0A            max = Math.max(max, Math.max(a, b));%0A        %7D%0A        memo%5Bindex%5D%5Brob ? 1 : 0%5D = max
 ;%0A  
@@ -915,16 +915,11 @@
 urn 
-val + m2
+max
 ;%0A  

Update problem 198