# Java commented DP solution

• Big Idea: Given any n, we make a guess k. Then we break the interval [1,n] into [1,k - 1] and [k + 1,n]. The min of worst case cost can be calculated recursively as

cost[1,n] = k + max{cost[1,k - 1] + cost[k+1,n]}
Also, it takes a while for me to wrap my head around "min of max cost". My understand is that: you strategy is the best, but your luck is the worst. You only guess right when there is no possibilities to guess wrong.

``````public class Solution {
public int getMoneyAmount(int n) {
// all intervals are inclusive
// uninitialized cells are assured to be zero
// the zero column and row will be uninitialized
// the illegal cells will also be uninitialized
// add 1 to the length just to make the index the same as numbers used
int[][] dp = new int[n + 1][n + 1]; // dp[i][j] means the min cost in the worst case for numbers (i...j)

// iterate the lengths of the intervals since the calculations of longer intervals rely on shorter ones
for (int l = 2; l <= n; l++) {
// iterate all the intervals with length l, the start of which is i. Hence the interval will be [i, i + (l - 1)]
for (int i = 1; i <= n - (l - 1); i++) {
dp[i][i + (l - 1)] = Integer.MAX_VALUE;
// iterate all the first guesses g
for (int g = i; g <= i + (l - 1); g++) {
int costForThisGuess;
// since if g is the last integer, g + 1 does not exist, we have to separate this case
// cost for [i, i + (l - 1)]: g (first guess) + max{the cost of left part [i, g - 1], the cost of right part [g + 1, i + (l - 1)]}
if (g == n) {
costForThisGuess = dp[i][g - 1] + g;
} else {
costForThisGuess = g + Math.max(dp[i][g - 1], dp[g + 1][i + (l - 1)]);
}
dp[i][i + (l - 1)] = Math.min(dp[i][i + (l - 1)], costForThisGuess); // keep track of the min cost among all first guesses
}
}
}
return dp[1][n];
}
}
``````

Any questions, suggestions & criticism welcomed!

• @myanonymos

a little improvement :)

``````public int getMoneyAmount(int n) {
int[][] dp = new int[n+1][n+1];
for(int len=1;len<n;len++){
for(int i=1;i+len<=n;i++){
int j=i+len;
int min = Integer.MAX_VALUE;
for(int k=i;k<j;k++){
int tmp = k+Math.max(dp[i][k-1],dp[k+1][j]);
min = Math.min(min,tmp);
}
dp[i][j] = min;
}
}
return dp[1][n];
}``````

• @juanren Awesome! Much Shorter and Neater than mine! You know what, I compared my code and yours and I laughed at myself when I saw I kept using i + (l - 1) instead of assigning it to a variable. How dumb was it! Haha!

• said in Java commented DP solution:

you strategy is the best, but your luck is the worst

"you strategy is the best, but your luck is the worst" This is the best explanation :)

• Hi, @juanren your code is concise and neat, but I think some of it could be a bit misleading;

1.the minimum valid length should 2, because we all know we don't have to cost a single penny to guarantee a win when i==j; and it cannot be explain by the code, we'd better leave it as a corner case;

2.in the for loop: "for(int i=1;i+len<=n;i++)", we'd better let it be "for(int i=1;i+length-1<=n;i++)" and "int j=i+len-1".

3.in the for loop "for(int k=i;k<j;k++)", it should be "for(int k=i;k<=j;k++)", because it's necessary to be able to pick j between i......j;

`````` public int getMoneyAmount(int n)
{
int[][] dp=new int[n+2][n+2];
for(int length=2;length<=n;length++)
{
for(int i=1;i+length-1<=n;i++)
{
int j=i+length-1;
int min=Integer.MAX_VALUE;
for(int k=i;k<=j;k++)
{
int temp=k+Math.max(dp[i][k-1],dp[k+1][j]);
min=Math.min(min, temp);
}
dp[i][j]=min;
}
}
return dp[1][n];
}
``````

though your version runs well, but that code above make more sense to me;

again your code is brilliant, thanks for sharing.

• @mustangigem Can you explain any more? What's our strategy? I think the strategy is explicit: when we got "higher", go to the higher half.

• The comments within your code really helps me a lot in understanding this problem! Thank you for such a good post!

• This post is deleted!

• This post is deleted!

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