# DP Solution which is similar to '312. Burst Balloons'

• 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.

1. 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`
2. 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`
3. 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];
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.