# Very quickly Java DP solution . O(n)

• ``````public class Solution {
private int[] getRight(Map<Integer,int[]> rdp,int pack) {
if ( rdp.containsKey(pack) )
return rdp.get(pack);
int sp = ( pack - 1 ) / 2 + 1;
int[] ret = getRight(rdp,sp);
int[] res = new int[] { ret[0] + 1 , ret[1]  + (sp<<2) + ((pack & 0x01) == 0 ?(sp<<2) * ret[0]:0) };
rdp.put(pack,res);
return res;
}
public int getMoneyAmount(int n) {
if ( n == 0 ) return 0;
if ( n <= 3 ) return n-1;
int dp[] = new int[n+1];
dp[0] = 0;dp[1] = 0; dp[2] = 1; dp[3] = 2;

Map<Integer,int[]>     rdp = new HashMap<Integer, int[]>();
rdp.put(1,new int[]{1,2});
rdp.put(2,new int[]{2,10});

for ( int i=4;i<=n;++i ) {
for ( int pack = 1; ; ++pack ) {
int ptr = i + 1 - pack * 4;
int left = dp[ptr-1];
int[] ret = getRight(rdp,pack);
int right = ret[0] * ptr + ret[1];
if ( right >= left ) {
if ( dp[i] == 0 || dp[i] > ptr + right )
dp[i] = ptr + right;
break;
}
dp[i] = ptr + left;
}
}
return dp[n];
}

}
``````

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