3ms Java DP solution


  • 11

    Similar to other DP solutions, but with two improvements.

    1. One more corner case: if the range is less or equal to 3 (start >= end - 2), the cost will be the upper boundary minus 1 (end - 1).
    2. When selecting the first guess, the loop starts from one index left to the middle ((start + end) / 2 - 1), and the loop break when the cost of left part is higher than the cost of right part.

    I think this problem is more similar to Burst Balloons #312.

    public class Solution {
        int[][] dp;
        public int getMoneyAmount(int n) {
            dp = new int[n + 1][n + 1];
            return helper(1, n);
        }
        
        private int helper(int start, int end) {
            if (dp[start][end] != 0) {
                return dp[start][end];
            }
            if (start >= end) {
                return 0;
            }
            if (start >= end - 2) {
                return dp[start][end] = end - 1;
            }
            int mid = (start + end) / 2 - 1, min = Integer.MAX_VALUE;
            while (mid < end) {
                int left = helper(start, mid - 1);
                int right = helper(mid + 1, end);
                min = Math.min(min, mid + Math.max(left, right));
                if (right <= left) break;
                mid++;
            }
            return dp[start][end] = min;
        }
        //runtime 3ms
    }
    

  • 0
    S

    The second optimization is really good, by observing the monotonicity of the left and right parts as well as the fact that dp[i][i+k] <= dp[j][j+k] if i <= j.


  • 0
    J

    Why choose one index left to the middle? The goal of this part should be ensure that at the beginning, the length of left part is less or equal to the right part, then setting the starting index as the middle (start + end) / 2 should be enough.


  • 0
    N

    @JiafengNi92 said in 3ms Java DP solution:

    Why choose one index left to the middle? The goal of this part should be ensure that at the beginning, the length of left part is less or equal to the right part, then setting the starting index as the middle (start + end) / 2 should be enough.

    Yes. I also want to point this out.
    Based on my observation, the optimal pick in each round would be the middle one or its later one.


  • 0

    Same idea:

    public class Solution {
    int[][] map;
    public int getMoneyAmount(int n) {
        map = new int[n+1][n+1];
        return getMoneyHelper(1, n);
    }
    public int getMoneyHelper(int start, int end){
        if(end - start>3){
            if(map[start][end]>0) return map[start][end];
            int Money = Integer.MAX_VALUE;
            for(int pick = (start+end)/2; pick <end; pick++){
                int left = getMoneyHelper(start, pick-1);
                int right = getMoneyHelper(pick+1, end);
                if(left<right) Money = Math.min(Money, pick + right);
                else {
                    Money = Math.min(Money, pick + left);
                    break;
                }
            }
            map[start][end] = Money;
            return Money;
        }
        else if(end - start==3) return end - 1 + end -3;
        else if(end - start>0) return end -1;
        else return 0;
    }
    }

Log in to reply
 

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