Bottom-up solution for both worst case and expected case.


  • 4
    L

    Original problem:

    • Try all possible guess i for a given n, we want to find out which i gives the minimum cost.
    • For each guess, you actually divide the original problem of size n into 2 smaller problem of size x and size (n - x). Smaller size problem needs to be solved first, larger size problem needs to look up the result of smaller size problem. Base case is size of 1, cost is 0, because you always guess correctly in the first try.
    • Use dynamic programming to solve (either bottom up or top down), be careful with edge cases when you guess is the first or the last element of the subproblem.
    • For strategy 1 (maximum loss you could possibly face): while you guess, ALWAYS assume:
    1. You guess the wrong number unless there is only one element left.
    2. The target number is hiding in one of the two subproblems that has a higher cost.

    Code:

    // solution for minimize the maximum (worst case) loss
    public static int solutionMax(int n) {
        // index 0 is not used for convenience
        int[][] dp = new int[n + 1][n + 1];
        int left = 0;
        int right = 0;
        int best = Integer.MAX_VALUE;
        int[][] moves = new int[n + 1][n + 1];
    
        for (int step = 1; step <= n - 1; step++) {
            for (int i = 1; i + step <= n; i++) {
                best = Integer.MAX_VALUE;
                for (int j = i; j <= i + step; j++) {
                    left = (j == i) ? 0 : dp[i][j - 1];
                    right = (j == i + step) ? 0 : dp[j + 1][i + step];
                    int bestofTwo = Math.max(left, right);
                    if (j + bestofTwo < best) {
                        best = bestofTwo + j;
                        moves[i][i + step] = j;
                    }
                }
                dp[i][i + step] = best;
            }
        }
    
        // for the purpose of printing moves only
        int curL = 1;
        int curR = n;
        System.out.println("worst case moves: ");
        while (dp[curL][curR] != 0) {
            int curM = moves[curL][curR];
            System.out.print(curM + " ");
            int curML = (curM == curL) ? curM : curM - 1;
            int curMR = (curM == curR) ? curM : curM + 1;
            if (dp[curL][curML] > dp[curMR][curR]) {
                curR = curML;
            } else {
                curL = curMR;
            }
        }
        System.out.println();
        // end of printing
    
        return dp[1][n];
    }
    

    Follow-up Problem:
    Everything is the same except the definition of loss function. In this case, change the assumption to:
    While you are guessing number i over problem size n:

    1. Consider all cases, including the case that you guess the correct number, which leads to zero cost.
    2. When guess is wrong, calculate the weighted loss for both subproblems, instead of taking the max, take the sum of the two weighted loss value.

    Code:

    // solution for minimize the maximum (worst case) loss
    public static double solutionExp(int n) {
        // index 0 is not used for convenience
        double[][] dp = new double[n + 1][n + 1];
        double weightedLeft = 0;
        double weightedRight = 0;
        double best = Double.MAX_VALUE;
        int[][] moves = new int[n + 1][n + 1];
    
        for (int step = 1; step <= n - 1; step++) {
            for (int i = 1; i + step <= n; i++) {
                best = Double.MAX_VALUE;
                for (int j = i; j <= i + step; j++) {
                    weightedLeft = 1.0 * ((j == i) ? 0 : dp[i][j - 1] + j)
                            * (j - i) / (step + 1);
                    weightedRight = 1.0
                            * ((j == i + step) ? 0 : dp[j + 1][i + step] + j)
                            * (i + step - j) / (step + 1);
                    double expectedCost = weightedLeft + weightedRight;
                    if (expectedCost < best) {
                        best = expectedCost;
                        moves[i][i + step] = j;
                    }
                }
                dp[i][i + step] = best;
            }
        }
    
        // for the purpose of printing moves only
        int curL = 1;
        int curR = n;
        System.out.println("worst case moves: ");
        while (dp[curL][curR] != 0) {
            int curM = moves[curL][curR];
            System.out.print(curM + " ");
            int curML = (curM == curL) ? curM : curM - 1;
            int curMR = (curM == curR) ? curM : curM + 1;
            if (dp[curL][curML] > dp[curMR][curR]) {
                curR = curML;
            } else {
                curL = curMR;
            }
        }
        System.out.println();
        // end of printing
    
        return dp[1][n];
    }
    
    

Log in to reply
 

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