Very quickly Java DP solution . O(n)


  • 0
    E
    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];
        }
    
    }
    

Log in to reply
 

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