多米诺骨牌

小橙子Chelsea · · 897 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

多米诺骨牌

image.png

结果:

image.png

分析过程:

  • 准备一个二维数组存储每个阶段的状态结果值
  • 将问题分解为前一个骨块和下一个骨块左右的关系
  • 找到递推关系

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)

}



有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:小橙子Chelsea

查看原文:多米诺骨牌

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

897 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传