Guess Number Higher or Lower II LeetCode solution in Java

1
class Solution {
2
  public int getMoneyAmount(int n) {
3
    int dp[][] = new int[n + 1][n + 1];
4
    for (int a[] : dp) {
5
      Arrays.fill(a, -1);
6
    }
7
    return solve(1, n, dp);
8
  }
9

10
  static int solve(int start, int end, int[][] dp) {
11
    if (start >= end) return 0;
12
    if (dp[start][end] != -1) return dp[start][end];
13
    int min = Integer.MAX_VALUE;
14
    for (int i = start; i <= end; i++) {
15
      min = Math.min(min, i + Math.max(solve(start, i - 1, dp), solve(i + 1, end, dp)));
16
    }
17
    dp[start][end] = min;
18
    return min;
19
  }
20
}