Java DP Solution with Optimization beats 97%


  • 0
    M
        public int getMoneyAmount(int n) {
            if(n<=1) return 0;
            int[][] dp = new int[n+1][n+1];
            recursion(dp, 1, n);
            return dp[1][n];
        }
        
        private int recursion(int[][] dp, int start, int end) {
            if(start>=end) return 0;
            if(dp[start][end]!=0) return dp[start][end];
            int minCost = Integer.MAX_VALUE;
            for(int i = (start + end)>>>1, left = 0, right = 1; i <= end && left<right; i++) { // start from mid, and if left part is equal to or greater than right part we could stop scanning
                left = recursion(dp, start, i-1);
                right = recursion(dp, i+1, end);
                int cost = i + Math.max(left, right);
                minCost = Math.min(minCost, cost);
            }
            dp[start][end] = minCost;
            return minCost;
        }
    

Log in to reply
 

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