这是我朋友昨天问我的一个问题，我相信这是他看到的一个面试问题。规则很简单，对于n=4，有5个不同的部分：
ooo
o
o
ooo
oo
oo
oooo
oo
oo
对于给定的
n，您需要计算不同片段的数量。这意味着这四个是相同的：
ooo o o o
o ooo o o
oo oo
当问题变得更复杂，我甚至不知道它属于哪种类型的问题时，我未能解决这个原因它看起来像一个dfs，但您可以同时选择多个目录。删除重复项也很重要。
最佳答案
以下是wiki的解决方案
每一个n+1级的多聚氨基都可以通过在n级的多聚氨基上加一个正方形来获得，这就产生了归纳生成多聚氨基的算法。
最简单的是，给定一个n阶多元数目的列表，在每个可能的位置，可以在每个多元数的旁边添加正方形，如果没有已经找到的重复项，则可以将得到的n+1阶多元数添加到列表中；在排序枚举和标记不应被视为减少案例数量的相邻正方形方面进行了改进需要检查是否存在重复项。[9]此方法可用于枚举自由的或固定的多胺。
Redelmeier描述的一种更为复杂的方法被许多作者用作一种不仅计算多聚氨基的方法（不要求存储n阶的所有多聚氨基以枚举n+1阶的多聚氨基），而且还证明了它们的数的上界基本思想是我们从一个正方形开始，然后从那里递归地添加正方形。根据细节，它可以从n个正方形中的每一个开始，对每个n-ominon计数一次，或者可以被安排为只对每个n-ominon计数一次。
最简单的实现是一次添加一个正方形。从一个初始正方形开始，从顶部顺时针给相邻的正方形编号1、2、3和4。现在选择一个介于1和4之间的数字，并在该位置添加一个正方形对未编号的相邻方块进行编号，从5开始然后，选择一个比先前选择的数字大的数字，并添加该正方形。继续选择一个大于当前正方形的数字，添加该正方形，然后对新的相邻正方形进行编号当n个方块被创建时，一个n-omino被创建。
这种方法确保每个固定的polymino精确计数n次，每个起始方一次。可以对其进行优化，使其只计算一次多聚氨基，而不是n次。从最初的正方形开始，声明它是polymino的左下角的正方形简单地说，不要给下一行的正方形或同一行正方形左边的正方形编号。这是redelmeier描述的版本。
如果你想计算自由多胺，那么你可以在创建每一个n-omino后检查对称性。然而，单独产生对称多胺（通过这种方法的一个变体）更快[10]，因此通过burnside引理确定自由多胺的数量。
Iwan Jensen发现了最新的枚举固定多氨基的算法。[12]对Andrew Conway方法的改进，[13]它比以前的方法快指数（但是，它的运行时间仍然是n的指数）。
Conway和Jensen的转移矩阵方法都涉及计算具有一定宽度的多胺的数量计算所有宽度的数量得到多聚氨基的总数。该方法的基本思想是考虑可能的起始行，然后确定完成给定宽度的polymino所需的最小平方数。结合生成函数的使用，该技术能够同时计算多个多聚氨基，从而使其运行速度比必须生成每个多聚氨基的方法快很多倍。
尽管该算法有很好的运行时间，但其折衷之处在于它使用了指数级的内存量（对于大于50的n，需要许多千兆字节的内存），比其他方法更难编程，并且目前不能用于计算自由多聚胺。
对我来说，这已经足够了不过，我真正想计算的是自由多胺的数量，但似乎没有简单的解决办法如果我在一次采访中被问到这个问题，我会给出上面提到的算法来计算固定多聚氨基的数量，然后删除重复的多聚氨基来计算自由多聚氨基。
关于algorithm - 俄罗斯方块的n个块的有效块，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32023393/