多米诺骨牌
结果:
分析过程:
- 准备一个二维数组存储每个阶段的状态结果值
- 将问题分解为前一个骨块和下一个骨块左右的关系
- 找到递推关系
result[0] = append(result[0], int64(math.Max(float64(result[0][i]+node.Rnext.L), float64(result[1][i]+node.Lnext.L))))
result[1] = append(result[1], int64(math.Max(float64(result[0][i]+node.Rnext.R), float64(result[1][i]+node.Lnext.R))))
golang代码:
package main
import (
"fmt"
"golang.guazi-corp.com/finance/lego/common/math"
)
type Node struct {
L int64
R int64
Status int64
}
func dynamic(list []Node) int64 {
//存储当前块的左右值和下一块的左边结果,右边结果中间值
result := [2][]int64{{0}, {0}}
for i := 0; i < len(list)-1; i++ {
node := list[i]
next := list[i+1]
result[0] = append(result[0], int64(math.Max(float64(result[0][i]+node.R*next.L), float64(result[1][i]+node.L*next.L))))
result[1] = append(result[1], int64(math.Max(float64(result[0][i]+node.R*next.R), float64(result[1][i]+node.L*next.R))))
}
sum := int64(0)
if result[0][len(result[0])-1] >= result[1][len(result[1])-1] {
sum = result[0][len(result[0])-1]
} else {
sum = result[1][len(result[1])-1]
}
for i := 1; i < len(result[0]); i++ {
if result[0][i] > result[1][i] {
list[i].Status = 1
}
}
return sum
}
func main() {
list := []Node{
{5, 8, 0},
{4, 2, 0},
{9, 6, 0},
{7, 7, 0},
{3, 9, 0},
{11, 10, 0},
}
sum := dynamic(list)
fmt.Println("sum=", sum)
fmt.Println(list)
}
有疑问加站长微信联系(非本文作者)