Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
给一个4行n列的棋盘每个单元格上都有一个整数。给定了2n盘的一部分，或者它们都可以放在棋盘上的一个不同的单元格上，因此总和是最大的。唯一的限制是两个磁盘不能在垂直或水平方向上相邻。如何使用DP将磁盘的最佳组合放置在O(n)中的板上？
最佳答案
第一，我们不能使用超过2×N的磁盘，因为任何列最多可以包含2个磁盘。
假设d[i] [掩码]最大填充量是从1到I填充磁盘后得到的，以便最后一列填充为掩码（掩码可以是0000, 0001、0010, 0100、0101, 1000、1001或1010，其中1表示磁盘，0表示不是）。
所以d[i][mask1]=max of（d[i-1][mask2]+在第i列应用mask1得到的数字），其中mask2可以是任何与mask1不矛盾的掩码
编辑1：您不需要更改任何内容当你在某个面具上的第i步时，它只取决于i-1面具的答案。你已经拥有了所有这些你只要试着从那些有效的数据中更新当前的d[i][mask]正如我已经说过的D[i]（掩码）-存储可以从1到i最佳填充列的最大值，使得最后一列具有这个掩码的形式（在第i列被填充之前不重要的面具，因为它们不会影响下一列）。
关于algorithm - 矩阵中子和元素的动态编程，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30335169/