This is question is similar to `312. Burst Balloons`

.

For these questions, we cannot come up with the solution intuitively, so we think about smaller examples first.

- range is
`0`

: if you guess a number from 1 to 1, you do not need to guess, so the min-cost is 0.`dp[i][i] = 0`

- range is
`1`

: if you guess a number from 1 to 2, you guess 1 and cost 1, or guess 2 and cost 2, so the min-cost is 2.`dp[i][i + 1] = i`

- range is
`2`

: if you guess a number from 1 to 3, you guess 1, or 2, or 3, using formula`dp[i][j] = min(k + max(dp[i][k - 1], dp[k + 1][j])) where k from (i + 1) to (j - 1)`

Here is the code, hope it helps!

```
public class Solution {
public int getMoneyAmount(int n) {
// dp[i][j] represents the min-cost of [i, j]
int[][] dp = new int[n + 1][n + 1];
for(int len = 1; len < n; len++) {
for(int left = 1; left <= n - len; left++) {
int right = left + len;
// Ex. for [1, 2], 1 is the min-cost
if(left + 1 == right) {
dp[left][right] = left;
continue;
}
// for [left, right], check every middle point
// max: whenever you choose a number, the feedback is always bad, and leads you to a worse branch.
// min: makes sure that you are minimizing your cost.
int min = Integer.MAX_VALUE;
for(int mid = left + 1; mid < right; mid++) {
int max = mid + Math.max(dp[left][mid - 1], dp[mid + 1][right]);
min = Math.min(min, max);
}
dp[left][right] = min;
}
}
return dp[1][n];
}
}
```