DP Solution which is similar to '312. Burst Balloons'


  • 0

    This is question is similar to 312. Burst Balloons.
    For these questions, we cannot come up with the solution intuitively, so we think about smaller examples first.

    1. range is 0: if you guess a number from 1 to 1, you do not need to guess, so the min-cost is 0. dp[i][i] = 0
    2. range is 1: if you guess a number from 1 to 2, you guess 1 and cost 1, or guess 2 and cost 2, so the min-cost is 2. dp[i][i + 1] = i
    3. range is 2: if you guess a number from 1 to 3, you guess 1, or 2, or 3, using formula dp[i][j] = min(k + max(dp[i][k - 1], dp[k + 1][j])) where k from (i + 1) to (j - 1)

    Here is the code, hope it helps!

    public class Solution {
        public int getMoneyAmount(int n) {
            // dp[i][j] represents the min-cost of [i, j]
            int[][] dp = new int[n + 1][n + 1];
            
            for(int len = 1; len < n; len++) {
                for(int left = 1; left <= n - len; left++) {
                    int right = left + len;
                    
                    // Ex. for [1, 2], 1 is the min-cost
                    if(left + 1 == right) {
                        dp[left][right] = left;
                        continue;
                    }
                    
                    // for [left, right], check every middle point
                    // max: whenever you choose a number, the feedback is always bad, and leads you to a worse branch.
                    // min: makes sure that you are minimizing your cost.
                    int min = Integer.MAX_VALUE;
                    for(int mid = left + 1; mid < right; mid++) {
                        int max = mid + Math.max(dp[left][mid - 1], dp[mid + 1][right]);
                        min = Math.min(min, max);
                    }
                    dp[left][right] = min;
                }
            }
            return dp[1][n];
        }
    }
    

Log in to reply
 

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