2021-04-29：给定一个数组 arr，代表一排有分数的气球。每打爆一个气球都能获得分数，假设打爆气 球 的分数为 X，获得分数的规则如下: 1)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L;如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 R。 获得分数为 L_X_R。 2)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L;如果被打爆气球的右边所有气球都已经被打爆。获得分数为 L_X。 3)如果被打爆气球的左边所有的气球都已经被打爆;如果被打爆气球的右边有没被打爆的 气球，找到离被打爆气球最近的气球，假设分数为 R;如果被打爆气球的右边所有气球都 已经 被打爆。获得分数为 X_R。 4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为 X。目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。【举例】arr = {3,2,5} 如果先打爆3，获得3_2;再打爆2，获得2_5;最后打爆5，获得5;最后总分21 如果先打爆3，获得3_2;再打爆5，获得2_5;最后打爆2，获得2;最后总分18 如果先打爆2，获得3_2_5;再打爆3，获得3_5;最后打爆5，获得5;最后总分50 如果先打爆2，获得3_2_5;再打爆5，获得3_5;最后打爆3，获得3;最后总分48 如果先打爆5，获得2_5;再打爆3，获得3_2;最后打爆2，获得2;最后总分18 如果先打爆5，获得2_5;再打爆2，获得3_2;最后打爆3，获得3;最后总分19 返回能获得的最大分数为50。
福大大 答案2021-04-29：
动态规划。
代码用golang编写。代码如下：
代码语言：txt复制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)
}
// 打爆arr[L..R]范围上的所有气球，返回最大的分数
// 假设arr[L-1]和arr[R 1]一定没有被打爆
func process(arr []int, L int, R int) int {
if L == R { // 如果arr[L..R]范围上只有一个气球，直接打爆即可
return arr[L-1] * arr[L] * arr[R 1]
}
// 最后打爆arr[L]的方案，和最后打爆arr[R]的方案，先比较一下
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))
// 尝试中间位置的气球最后被打爆的每一种方案
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
}
}执行结果如下：
图片***
左神java代码
