python – 用动态编程修补棋盘格
我正在尝试自学动态编程,并从麻省理工学院遇到这个问题.
我们给了一个棋盘,它有4行和n列,和 (a)确定任何一栏中可能出现的法律模式的数量(孤立地,无视) (b)使用兼容性和类型的概念,给出用于计算最佳放置的O(n)时动态编程算法. 好的,所以对于第一部分:有8种可能的解决方案. 对于b部分,我不确定,但这是我要去的地方: 我不知道从哪里开始.我意识到网上有这个问题的解决方案,但解决方案对我来说似乎不太清楚. 解决方法
你走在正确的轨道上.当您检查每个新列时,您将最终计算到目前为止所有可能的最佳分数.
假设您构建了兼容性列表(2D数组)并将其称为Li [y],使得对于每个模式,我有一个或多个兼容模式Li [y]. 现在,您检查列j.首先,您为每个模式计算该列的孤立分数i.称之为Sj [i].对于每个模式我兼容 此外,您还可以存储导致每个分数的pebbling模式.当您更新Cj [x](即您将其得分从其当前值增加)时,请记住导致更新的初始和后续模式为Pj [x] = i.这表示“模式x给出了最好的结果,给出了前面的模式我”. 当你完成所有的工作后,只需找到具有最高分Cn [i]的模式i.然后,您可以使用Pj回溯以从每个列中恢复导致此结果的pebbling模式. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |