矩阵中的子和元素的动态编程

给定一个4行棋盘和n列。在每个单元格中都有一个整数。鉴于2n光盘，其中的一部分，或者他们都可以放在板上的不同单元，所以总和是最大的。唯一的限制是2个碟片不能相互垂直或水平相邻。如何使用DP在O(n)上将最佳光盘组合放置在电路板上？矩阵中的子和元素的动态编程

来源

2015-05-19 itorra

所以我已经说过，每列有7种可能性模式（不放置光盘不是一个选项导致问题说部分）。我创建了一个矩阵M，如果我可以在列i + 1旁边放置一个列为c（可以是0到6）的列，将输出T或F.所以我想安排n个优先级队列大小为7，队列中的每个元素都是一对分类和来自该分类的数字的总和，在这里我卡住了 – itorra

为什么要使用优先级队列？试着想想你会如何将其作为一个DP来制定。您希望找到描述如何构建解决方案的重现。从简单开始：如果对我们可以在哪里放置光盘的位置没有限制，您将如何制定DP？ –

所以我想到sum（n）= sum（n-1）+ max {pik：k从0到可能模式的数量}。（p - 当前列）问题是每当我需要插入条件时我不能回头改变整个子问题 – itorra

1，我们不可能使用多于2 * n的磁盘，因为任何列最多可以包含2个磁盘。

比方说，d [i] [掩码] - 用磁盘填充从1到i的列后获得的最大数量，以便最后一列填充为掩码（掩码可以是0000，0001，0010，0100，0101，1000 ，1001或1010，其中1表示磁盘被放置，0表示它不是）

因此，d [i] [mask1] =（d [i-1] [mask2]的最大值+第2列），其中掩码2可以是与掩码1不抵触的任何掩码1

编辑1：您不需要更改任何内容。当你在某个面具上的第i步时，它仅取决于i-1的面具的答案。而你已经拥有了所有这些。你只是尝试从当前有效的d [i] [mask]中更新。正如我已经说过的那样d [i] [mask] - 存储可以从1到i填充列的最大值，最佳地使最后一列具有此掩码形式的磁盘（在我之前没有掩码因为它们不会影响下一列）

来源

2015-05-20 04:19:20 Herokiller

假设在第i列应用mask1得到的数字非常大，而mask1与mask2矛盾，我在哪里检查如何改变子问题中的所有内容，以便我可以在d [i] [mask1 ]？ – itorra

@itorra更新了我的答案。也许如果你有一个例子，我可以解释一下 – Herokiller

矩阵中的子和元素的动态编程

回答

相关问题