# Try One dimension DP

• 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;
}
``````

'''

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