use*_*074 8 python algorithm dynamic-programming
我正在尝试自学动态编程,并从麻省理工学院遇到这个问题.
我们给出了一个棋盘,它有4行和n列,每个正方形都有一个整数.我们还给了一组2n个鹅卵石,我们想要将一些或所有这些放在棋盘上(每个鹅卵石可以放在一个正方形上),以便最大化被覆盖的方块中的整数之和.鹅卵石.有一个约束:对于合法的鹅卵石放置,其中没有两个可以在水平或垂直相邻的方块上(对角线邻接是可以的).
(a)确定任何列中可能出现的合法模式的数量(孤立地,忽略相邻列中的鹅卵石)并描述这些模式.如果可以将两个模式放在相邻列上以形成合法放置,则调用两个模式兼容.让我们考虑由第一个k列1 k n组成的子问题.可以为每个子问题分配一个类型,即最后一列中出现的模式.
(b)使用兼容性和类型的概念,给出用于计算最佳放置的O(n)时动态编程算法.
好的,所以对于第一部分:有8种可能的解决方案.
对于b部分,我不确定,但这就是我要去的地方:SPlit into sub-problems.假设我在n.1.通过列0,...,i来定义Cj [i]为最佳值,使得列i具有模式类型j.2.为每种模式类型创建8个单独的n个元素数组.
我不知道从哪里开始.我意识到网上有这个问题的解决方案,但解决方案对我来说似乎不太清楚.
您走在正确的轨道上。当您检查每个新列时，最终将计算出所有可能的最佳分数。
假设您建立了兼容性列表（一个2D数组），并将其命名为L i [y]，这样对于每个模式i，都有一个或多个兼容模式L i [y]。
现在，您检查列j。首先，为每种模式i计算该列的孤立分数。称之为S j [i]。对于每个模式我和兼容模式X = L 我 [Y] ，需要最大化总得分Ç Ĵ使得Ç Ĵ [X] = C j-1 [I] + S Ĵ [X] 。这是一个简单的数组测试和更新（如果更大）。
此外，您还存储了导致每个得分的令人讨厌的模式。当更新C j [x]（即，从其当前值增加其分数）时，请记住引起更新的初始模式和后续模式为P j [x] = i。这就是说，“ 给定前面的模式i，模式x给出了最佳结果”。
完成后，只需找到得分最高的模式i C n [i]即可。然后，您可以使用P j回溯以从导致该结果的每一列中恢复研磨模式。