There are two dimensions DP Solutions so far, and their time complexity is O(n3). I tried an One dimension DP whoes time complexity is O(n2).

The code partially passed. It passed 10/13 test cases. FYI.

It would be great if anyone know how to modify the code to pass all test cases.

'''

```
public int getMoneyAmount(int n) {
int[] guess = new int[n+1];
int[] count = new int[n+1];
for (int i=2; i<=n; i++){
guess[i] = Integer.MAX_VALUE;
count[i] = Integer.MAX_VALUE;
for (int pos = 1; pos<=i; pos++){
/*split at pos, left guess[pos-1], right guess[i-pos] (need shift)
*/
int left = guess[pos-1],
right = shift(guess[i-pos], count[i-pos], pos);
int splitCost = pos + Math.max(left, right);
if (splitCost <= guess[i]){
guess[i] = splitCost;
count[i] = Math.min(count[i], 1 + Math.max(count[pos-1], count[i-pos]));
}
}
}
return guess[n];
}
int shift(int sum, int n, int offset){
sum += offset * n;
return sum;
}
```

'''