package leetcode;

/**
 * https://leetcode.com/problems/guess-number-higher-or-lower-ii/
 */
public class Problem375 {
    public int getMoneyAmount(int n) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem375 prob = new Problem375();
        System.out.println(prob.getMoneyAmount(10)); // 16
        System.out.println(prob.getMoneyAmount(15)); // 30
        System.out.println(prob.getMoneyAmount(5)); // 6
    }
}
@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -212,32 +212,55 @@
     
-// TODO%0A        return 0
+return getMoneyAmount(n, 1, n, new HashMap%3C%3E())
 ;%0A  
@@ -273,21 +273,22 @@
    p
-ublic
+rivate
  static 
 void
@@ -287,253 +287,553 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem375 prob = new Problem375();%0A        System.out.println(prob.getMoneyAmount(10)); // 16%0A        System.out.println(prob.getMoneyAmount(15)); // 30%0A        System.out.println(prob.getMoneyAmount(5)); // 6
+int getMoneyAmount(int n, int start, int end, Map%3CString, Integer%3E memo) %7B%0A        if (start %3E= end) %7B%0A            return 0;%0A        %7D%0A        String key = start + %22%7C%22 + end;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        int min = Integer.MAX_VALUE;%0A        for (int i = start; i %3C= end; i++) %7B%0A            int max = Math.max(getMoneyAmount(n, start, i - 1, memo), getMoneyAmount(n, i + 1, end, memo)) + i;%0A            min = Math.min(min, max);%0A        %7D%0A        memo.put(key, min);%0A        return min;
 %0A   

Solve problem 375