Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. The subject

There are n balloons, numbered from 0 to n-1, and each balloon is marked with a number, which is stored in the array NUMs.

Now you’re required to pop all the balloons. Pop the I th balloon and you get nums[I-1] * NUMs [I] * NUMs [I + 1] coins. I minus 1 and I plus 1 are the numbers of the two balloons next to I. If I – 1 or I + 1 goes beyond the bounds of the array, consider it a balloon with a number of 1.

Find the maximum number of coins you can get.

Example 1: input: nums = [3,1,5,8] output: 167 ,1,5,8 nums = [3] - > [3,5,8] - > [3] - > [8] - > [] COINS = 3 * 1 * 5 + 3 * 5 * 8 + 1 * 3 * 1 * 8 * 8 + 1 = 167 example 2: input: Nums = [1,5] output: 10Copy the code

2.

When it comes to finding the best value, the first thing that comes to mind is to enumerate all possible results and then compare and get the best value.

There are mainly two kinds of exhaustive algorithms, namely backtracking algorithm and dynamic programming.

2.1 Backtracking algorithm

If you use a backtracking algorithm, it’s essentially just picking the order in which you poke the balloon, and different pricks might get different scores, and then you find the highest score. The pseudo-codes are as follows:

int res = Integer.MIN_VALUE;
/* Enter a group of balloons and return the maximum score for poking them */
int maxCoins(int[] nums) {
    backtrack(nums, 0); 
    return res;
}
/* Backtracking algorithm of the pseudo-code solution */
void backtrack(int[] nums, int socre) {
    if(nums is empty) {res =max(res, score);
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        int point = nums[i- 1] * nums[i] * nums[i+1];
        int temp = nums[i];
        / / to make a choiceDelete element nums[I] from nums// recursive backtracking
        backtrack(nums, score + point);
        // Undo the selectionRestore temp to nums[I]}}Copy the code

But obviously, the efficiency of the algorithm is not high, and the time complexity is factorial level.

2.2 Dynamic Planning

The key point here is that for each balloon nums[I] punctured, the score obtained is correlated with the adjacent balloon NUMs [i-1] and NUMs [I +1].

First, we need to figure out how to define this subproblem, which is how to define dp arrays. Nums [-1] = nums[n] = 1

int maxCoins(int[] nums) {
    int n = nums.length;
    // Add two virtual balloons to both ends
    int[] points = new int[n + 2];
    points[0] = points[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
        points[i] = nums[i - 1];
    }
    // ...
}
Copy the code

Balloons are now indexed from 1 to N, points[0] and points[n+1] can be considered as two virtual balloons. The problem then translates to popping all balloons between 0 and n+1 in one exhaust ball points. How many points can I get?

So, the meaning of dp array can be defined as: dp[I][j] = x means that the highest score can be obtained by poking all balloons between balloon I and balloon J (open interval, excluding I and j) is X.

Basecase is dp[I][j] = 0, 0 <= I <= N +1, j <= I +1. In the case of the open interval (I, j), there is no balloon to prick at all.

Next, to determine the state transition equation, we assume that the last balloon punctured is K, then the value of dp[I][j] = DP [I][k] + dp[k][j] + points[I]*points[k]*points[j] First, the balloons in the open interval (I, k) are pricked (the score is dp[I][k]), and then the balloons in the open interval (k, j) are pricked (the score is DP [k][j]). Points [I]*points[k]*points[j]

So the final state transition equation:

// Which balloon popped last?
for (int k = i + 1; k < j; k++) {
    // Select the best option to make dp[I][j] maximum
    dp[i][j] = Math.max(
        dp[i][j], 
        dp[i][k] + dp[k][j] + points[i]*points[j]*points[k]
    );
}
Copy the code

And then I’ll exhaust states I and J, as follows

for (int i = ...; ; )
    for (int j = ...; ; )
        for (int k = i + 1; k < j; k++) {
            dp[i][j] = Math.max(
                dp[i][j], 
                dp[i][k] + dp[k][j] + points[i]*points[j]*points[k]
            );
return dp[0][n+1];
Copy the code

The code level diagram is derived as follows:

First, basecase is drawn on the DP table as follows:

In this process, the direction of the traversal is as follows :(since we specify I <j)

So, the complete code looks like this:

int maxCoins(int[] nums) {
    int n = nums.length;
    // Add virtual balloons on both sides
    int[] points = new int[n + 2];
    points[0] = points[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
        points[i] = nums[i - 1];
    }
    // Base cases are already initialized to 0
    int[][] dp = new int[n + 2][n + 2];
    // Start state transition
    // I should go from the bottom up
    for (int i = n; i >= 0; i--) {
        // j should go from left to right
        for (int j = i + 1; j < n + 2; j++) {
            // Which balloon popped last?
            for (int k = i + 1; k < j; k++) {
                // Choose according to the best
                dp[i][j] = Math.max( dp[i][j], dp[i][k] + dp[k][j] + points[i]*points[j]*points[k] ); }}}return dp[0][n + 1];
}
Copy the code

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream