LC 312. Burst Balloons

Topic describes

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = NUMs [n] = 1. They are not real therefore You can not burst them. 0 ≤ n ≤ 500, 0 ≤ NUMS [I] ≤ 100


Thinking analysis and code

When I got this problem, I could see from the description of the problem that was finally required to be solved that there were subproblems, and the final solution was “maximum”, so I could think of using dynamic programming to solve it, but the difficulty was how to define the state. What is the recursive equation? The number of numbers in the array is changing dynamically. If you think directly from the idea of dynamic programming, it is difficult to see what the relationship between the current problem and the previous sub-problem is. Therefore, depth-first search for violence can be considered first, but here are two ideas:

  • The balloon under consideration is the first to pop
  • The balloon under consideration is the last to pop

The first way is actually the easiest way to understand, but when you’re writing code you’ll find a lot of problems, like how do you know what the next number to the right and to the left is? You can do this by removing the number from the array, but this increases time and is not efficient. If the balloon number is I, then the balloon above the interval [0,i-1] and [I +1,n-1] has been exploded. The answer here is 1* I *1 + the solution of [0,i-1] + the solution of [I +1,n-1]. Such a problem is divided into two sub-problems. Subproblems can be broken down further

i [0,i-1] [i+1,n-1] ... . Ans (0, n - 1) = Max (nums nums [1] * [0] * nums [1] + ans (1, n - 1), / / the last dozen 0 ans balloon (0, 0) + nums nums [0] * * nums [1] [2] + ans (2, n - 1), / / the last dozen balloons ans 1 (0, 1) + nums * nums [1] [2] * nums [3] + ans (3, n - 1), / / the last play 2 balloons... Ans (0, n - 3) + nums [n - 3] * nums nums [n - 2) * (n - 1) + ans (n - 1, n - 1), / / the last play n - 2 balloon ans (0, n - 2) + nums nums [n - 2) * (n - 1) * nums [n]. // The last balloon is n-1.where nums[-1] == nums[n] == 1
Copy the code


Here, you can see that this idea is very similar to divide-and-conquer. It is, and that’s what makes this problem special. It’s actually a combination of dynamic programming and divide-and-conquer.

public int maxCoins(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    return helper(nums, 0, nums.length - 1);
}

private int helper(int[] nums, int l, int r) {
    if (l > r) {
        return 0;
    }
    
    int max = nums[l];
    for (int i = l; i <= r; ++i) {
        int cur = helper(nums, l, i - 1)
                    + get(nums, l - 1) * nums[i] * get(nums, r + 1)
                    + helper(nums, i + 1, r);
        
        max = Math.max(max, cur);
    }
    
    return max;
}

private int get(int[] nums, int i) {
    if (i < 0 || i >= nums.length) {
        return 1;
    }
    
    return nums[i];
}
Copy the code


The above code is very concise, the inside of the core code is for loop recursion, but note that this is just the solution to violence, violence is because it made a lot of have done before, it is not necessary to repeat operation, you can tell from before the recurrence formula as you can see, or you can draw a recursive tree view. Just adding an array to help keep track of what you’ve done before is a huge efficiency boost

public int maxCoins(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int[][] dp = new int[nums.length][nums.length];
    
    return helper(nums, dp, 0, nums.length - 1);
}

private int helper(int[] nums, int[][] dp, int l, int r) {
    if (l > r) {
        return 0;
    }
    
    if(dp[l][r] ! =0) {
        return dp[l][r];
    }
    
    int max = nums[l];
    for (int i = l; i <= r; ++i) {
        int cur = helper(nums, dp, l, i - 1)
                    + get(nums, l - 1) * nums[i] * get(nums, r + 1)
                    + helper(nums, dp, i + 1, r);
        
        max = Math.max(max, cur);
    }
    
    dp[l][r] = max;
    
    return max;
}

private int get(int[] nums, int i) {
    if (i < 0 || i >= nums.length) {
        return 1;
    }
    
    return nums[i];
}
Copy the code


In fact, the above code implementation has used the dynamic planning, but is the use of recursive implementation, at this time we go back to the dynamic planning inside the “state” and “recursive formula” at a glance:

Dp [I] [j] - > [I, j] input array interval on the maximum of dp (0, n - 1] = Max (nums nums [1] * [0] * nums [1] + dp (1, n - 1), Dp nums [0, 0] + [0] * nums * nums [1] [2] + dp (2, n - 1), dp [0, 1] + nums * nums [1] [2] * nums [3] + dp (3, n - 1),... dp[0,n-3]+nums[n-3]*nums[n-2]*nums[n-1]+dp[n-1,n-1], dp[0,n-2]+nums[n-2]*nums[n-1]*nums[n], );Copy the code

With the definition of states and the recursive formula, we can go straight to hands-on dynamic programming, but pay attention to the boundary conditions:

public int maxCoins(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int[] newNums = new int[nums.length + 2];
    
    newNums[0] = newNums[nums.length + 1] = 1;
    for (int i = 0; i < nums.length; ++i) {
        newNums[i + 1] = nums[i];
    }
    
    int n = newNums.length;
    
    int[][] dp = new int[n][n];

    for (int i = 2; i < n; ++i) {
        for (int l = 0; l < n - i; ++l) {
            int r = l + i;
            for(int j = l + 1; j < r; ++j) { dp[l][r] = Math.max(dp[l][r], newNums[l] * newNums[j] * newNums[r] + dp[l][j] + dp[j][r]); }}}return dp[0][n - 1];
}
Copy the code

This is a two-dimensional dynamic program, and if you were to graph the DP array on a sheet of paper, you would see that you’re only recording the upper triangle of the two-dimensional matrix, which is half the diagonal axis; The recording sequence is not line by line, but in a diagonal line.


conclusion

And you can see here that one of the ways we’re going to solve this problem is

  1. Think about and implement the violence solution
  2. Draw a tree or think about repeating subproblems
  3. On the basis of the solution of violence, see if we can increase the memorization, record the solution of the subproblem solved before
  4. Using state and recursive formulas, try dynamic programming

Often encounter can not get the optimal algorithm all of a sudden, or there is no idea of the problem, you can try this step. Often dynamic programming can solve the problem, violent search can be solved, but the reverse is not necessarily. Just to say that violence search it is not our end, but it can provide us with a good breakthrough, we on this basis to think about how to further optimize, we finally want to see the algorithm. Continue to master this process and believe that thinking and intuition will improve involuntarily.

Another is the problem of a very clever place is added in the idea of partition, partition algorithm and dynamic programming algorithm for different places, or the opposite, partition that there is no repeat of subproblems, don’t understand can think quick sort, an interval is divided, separated two interval does not exist any intersection, They do things in their own space; Because of this, when thinking about the solution of violence, according to the idea of divide and conquer, the direction of choice is from the results-oriented, backwards to think, first divided and then combined, divided until can not be divided, and then to merge, for this problem, merge is very simple, that is, add; But if we follow the thinking of general dynamic programming, then after blowing up a balloon, the left and right sections of the balloon will converge, which cannot turn a problem into a smaller problem to solve. Although this way of thinking broke our usual way of thinking, but still that sentence, more accumulation, now will not be later, see more is not afraid.