My solution is accepted when n between 1-123, when n>124,**the outputs differ from the test program, and I couldn't find the mistake.** So please help me solve it. I suspect if the test case has some wrong.

This is my test inputs and outputs:

My thinking process about this question :

I used res[] for storing the all results if inputting 1 to n

The target is to try to find the *minimum* of the *max* between **split index + res[split index - 1]** and **right part**(including split index)

and for a certain i (1-n) , I use j to travel from i-1 to 1 to find **split index**

since we need n-1 to check whether it is n, we need n-3(n-1-2) to check whether it is bigger than n-3......

so each step I record the sum of **split index**s i-1, i-1-2, i-1-2-4,..., i-1-2-4-2^m as **right part**

left part is **split index + res[split index - 1]**

so with the vary of j, I could record the minimum as **res[i]**

```
public class Solution {
public int getMoneyAmount(int n) {
int[] res = new int[n+1];
for(int i=2; i<=n; i++){
res[i] = Integer.MAX_VALUE;
int right = 0, k=1;
for(int j=i-k; j>0; j-=k){
right += j;
k *= 2;
if(j+res[j-1] > right) {
res[i] = Math.min(res[i], j+res[j-1]);
}
else {
res[i] = Math.min(res[i], right);
}
}
}
return res[n];
}
}
```

I checked the result when input is 124, it should be **res[108] + 109 = 557**, (and 109 = 124-15 (1+2+4+8)) in my way.

Could you find the 555 solution according to the test case.

What I missed?