2021-04-29: given an array arr, it represents a row of balloons with scores. One for each blow

2021-04-29： Given an array arr, Represents a row of balloons with scores . Every time you blow up a balloon, you get a score , Suppose you blow up the gas The ball The score of is X, The rules for obtaining scores are as follows : 1) If there is an unexploded balloon on the left of the exploded balloon , Find the balloon closest to the exploded balloon , Suppose the score is L; If there is an unexploded balloon on the right of the exploded balloon , Find the balloon closest to the exploded balloon , Suppose the score is R. Get a score of L_X_R. 2) If there is an unexploded balloon on the left of the exploded balloon , Find the balloon closest to the exploded balloon , Suppose the score is L; If all the balloons on the right of the exploded balloon have been exploded . Get a score of L_X. 3) If all the balloons on the left of the exploded balloon have been exploded ; If there is one on the right side of the balloon that has been blasted balloon , Find the balloon closest to the exploded balloon , Suppose the score is R; If all the balloons to the right of the exploded balloon are already Be blasted . Get a score of X_R. 4) If all the balloons on the left and right of the exploded balloon have been exploded . Get a score of X. The goal is to blow up all the balloons , Get the score of each explosion . By choosing the order in which the balloons are blasted , You can get different total scores , Please return the maximum score you can get .【 give an example 】arr = {3,2,5} If you blow it up first 3, get 3_2; Blast again 2, get 2_5; Finally explode 5, get 5; The final total score 21 If you blow it up first 3, get 3_2; Blast again 5, get 2_5; Finally explode 2, get 2; The final total score 18 If you blow it up first 2, get 3_2_5; Blast again 3, get 3_5; Finally explode 5, get 5; The final total score 50 If you blow it up first 2, get 3_2_5; Blast again 5, get 3_5; Finally explode 3, get 3; The final total score 48 If you blow it up first 5, get 2_5; Blast again 3, get 3_2; Finally explode 2, get 2; The final total score 18 If you blow it up first 5, get 2_5; Blast again 2, get 3_2; Finally explode 3, get 3; The final total score 19 The maximum score you can get is 50.

Fuda answer 2021-04-29：

Dynamic programming .

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
)

func main() {
    arr := []int{2, 2, 2}
    ret := maxCoins1(arr)
    fmt.Println(ret)

    ret = maxCoins2(arr)
    fmt.Println(ret)
}

func maxCoins1(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    if len(arr) == 1 {
        return arr[0]
    }
    N := len(arr)
    help := make([]int, N+2)
    help[0] = 1
    help[N+1] = 1
    for i := 0; i < N; i++ {
        help[i+1] = arr[i]
    }
    return process(help, 1, N)
}

//  Explode arr[L..R] All balloons in range , Returns the maximum score 
//  hypothesis arr[L-1] and arr[R+1] It must not have been blown up 
func process(arr []int, L int, R int) int {
    if L == R { //  If arr[L..R] There is only one balloon in the range , Just blow it up 
        return arr[L-1] * arr[L] * arr[R+1]
    }
    //  Finally explode arr[L] The plan , And finally explode arr[R] The plan , Let's compare 
    max := getMax(arr[L-1]*arr[L]*arr[R+1]+process(arr, L+1, R),
        arr[L-1]*arr[R]*arr[R+1]+process(arr, L, R-1))
    //  Try every scheme in which the balloon in the middle is finally blown up 
    for i := L + 1; i < R; i++ {
        max = getMax(max, arr[L-1]*arr[i]*arr[R+1]+process(arr, L, i-1)+process(arr, i+1, R))
    }
    return max
}

func maxCoins2(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    if len(arr) == 1 {
        return arr[0]
    }
    N := len(arr)
    help := make([]int, N+2)
    help[0] = 1
    help[N+1] = 1
    for i := 0; i < N; i++ {
        help[i+1] = arr[i]
    }
    dp := make([][]int, N+2)
    for i := 0; i < N+2; i++ {
        dp[i] = make([]int, N+2)

    }
    for i := 1; i <= N; i++ {
        dp[i][i] = help[i-1] * help[i] * help[i+1]
    }
    for L := N; L >= 1; L-- {
        for R := L + 1; R <= N; R++ {
            ans := help[L-1]*help[L]*help[R+1] + dp[L+1][R]
            ans = getMax(ans, help[L-1]*help[R]*help[R+1]+dp[L][R-1])
            for i := L + 1; i < R; i++ {
                ans = getMax(ans, help[L-1]*help[i]*help[R+1]+dp[L][i-1]+dp[i+1][R])
            }
            dp[L][R] = ans
        }
    }
    return dp[1][N]
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

The results are as follows ：

picture

***

Zuo Shen java Code