Similar to other DP solutions, but with two improvements.

- One more corner case: if the range is less or equal to 3 (start >= end - 2), the cost will be the upper boundary minus 1 (end - 1).
- When selecting the first guess, the loop starts from one index left to the middle ((start + end) / 2 - 1), and the loop break when the cost of left part is higher than the cost of right part.

I think this problem is more similar to Burst Balloons #312.

```
public class Solution {
int[][] dp;
public int getMoneyAmount(int n) {
dp = new int[n + 1][n + 1];
return helper(1, n);
}
private int helper(int start, int end) {
if (dp[start][end] != 0) {
return dp[start][end];
}
if (start >= end) {
return 0;
}
if (start >= end - 2) {
return dp[start][end] = end - 1;
}
int mid = (start + end) / 2 - 1, min = Integer.MAX_VALUE;
while (mid < end) {
int left = helper(start, mid - 1);
int right = helper(mid + 1, end);
min = Math.min(min, mid + Math.max(left, right));
if (right <= left) break;
mid++;
}
return dp[start][end] = min;
}
//runtime 3ms
}
```