最高的广告牌。你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。返回广告牌的最大可能安装高度。如果没法安装广告牌,请返回 0。
时间紧,见代码。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
rods := []int{1, 2, 3, 6}
ret := tallestBillboard(rods)
fmt.Println(ret)
}
func tallestBillboard(rods []int) int {
// key 集合对的某个差
// value 满足差值为key的集合对中,最好的一对,较小集合的累加和
// 较大 -> value + key
dp := make(map[int]int)
dp[0] = 0 // 空集 和 空集
var cur map[int]int
for _, num := range rods {
if num != 0 {
// cur 内部数据完全和dp一样
cur = make(map[int]int) // 考虑x之前的集合差值状况拷贝下来
for k, v := range dp {
cur[k] = v
}
for d, _ := range cur {
diffMore := cur[d] // 最好的一对,较小集合的累加和
// x决定放入,比较大的那个
dp[d+num] = getMax(diffMore, dp[num+d])
// x决定放入,比较小的那个
// 新的差值 Math.abs(x - d)
// 之前差值为Math.abs(x - d),的那一对,就要和这一对,决策一下
// 之前那一对,较小集合的累加和diffXD
diffXD := dp[Abs(num-d)]
if d >= num { // x决定放入比较小的那个, 但是放入之后,没有超过这一对较大的那个
dp[d-num] = getMax(diffMore+num, diffXD)
} else { // x决定放入比较小的那个, 但是放入之后,没有超过这一对较大的那个
dp[num-d] = getMax(diffMore+d, diffXD)
}
}
}
}
return dp[0]
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func Abs(a int) int {
if a < 0 {
return -a
} else {
return a
}
}
执行结果如下: