给定一个4行n列的棋盘。每个单元格都有一个整数。给定2n盘，它们的一部分，或者全部，你可以把它们放在棋盘上的不同格上，这样总数是最大的。唯一的限制是两个光盘不能在垂直或水平方向相邻。如何使用DP在O(n)板上放置最佳的光盘组合?
首先，我们不可能使用超过2*n个磁盘，因为任何列最多只能包含2个磁盘。
让我们说d[i][mask] -在从1到1的列中填充磁盘后获得的最大数量，以便最后一列被填充为掩码(掩码可以是0000,0001,0010,0100,0101,1000,1001或1010，其中1表示磁盘被放置，0表示没有)
则d[i][mask1] = max (d[i-1][mask2] +在第i列上应用mask1得到的数)，其中mask2可以是任何与mask1不矛盾的掩码
编辑1:你不需要改变任何东西。当你在某个掩码的第i步时，它只取决于第i-1个掩码的答案。而你已经拥有了所有这些。你只是尝试从那些有效的更新当前的d[i][mask]。正如我已经说过的，d[I][mask] -存储从1到I填充列所能获得的最大值，最理想的是，这样最后一列就有了这个掩码形式的磁盘(在第I列被填充之前的掩码无关紧要，因为它们不会影响下一列)