如何开始“无裂墙”问题

Question

这里是问题说明：

[考虑用2x1和3x1砖（水平x垂直尺寸）建造墙的问题，以便获得额外的强度，水平砖之间的缝隙不会连续排列，即不会形成“运行裂缝” 。

有八种方法来形成无裂缝的9x3墙，写为W（9,3）= 8。

计算W（32,10）。

http://www.careercup.com/question?id=67814&form=comments

上面的链接提供了一些解决方案，但是我无法理解它们背后的逻辑。我正在尝试用Perl编写代码，到目前为止已经完成了：

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)            # C:combinations

将所有这些n相加应得出所有可能组合的计数。但是我不知道如何找到一行的真正组合以及如何进一步进行。

Answer 1

基于W（9,3）= 8的说法，我推断“运行裂纹”是指高度为2或更大的任何连续垂直裂纹。在解决所提出的二维问题之前，我想讨论一个类似的一维问题及其解决方案。我希望这将使我们更清楚地将二维问题视为一维问题并最终得到解决。

Answer 2

我在线上找到了这个python代码here，它可以快速正确地运行。我不明白这是怎么回事。我可以将C ++转到最后一步（计算解决方案的总数），并且无法使其正常工作。

def brickwall(w,h):
    # generate single brick layer of width w (by recursion)
    def gen_layers(w):
        if w in (0,1,2,3):
            return {0:[], 1:[], 2:[[2]], 3:[[3]]}[w]
        return [(layer + [2]) for layer in gen_layers(w-2)] + \
               [(layer + [3]) for layer in gen_layers(w-3)]
    # precompute info about whether pairs of layers are compatible
    def gen_conflict_mat(layers, nlayers, w):
        # precompute internal brick positions for easy comparison
        def get_internal_positions(layer, w):
            acc = 0; intpos = set()
            for brick in layer:
                acc += brick; intpos.add(acc)
            intpos.remove(w)
            return intpos
        intpos = [get_internal_positions(layer, w) for layer in layers]        
        mat = []
        for i in range(nlayers):
            mat.append([j for j in range(nlayers) \
                              if intpos[i].isdisjoint(intpos[j])])
        return mat
    layers = gen_layers(w)
    nlayers = len(layers)
    mat = gen_conflict_mat(layers, nlayers, w)
    # dynamic programming to recursively compute wall counts
    nwalls = nlayers*[1]
    for i in range(1,h):
        nwalls = [sum(nwalls[k] for k in mat[j]) for j in range(nlayers)]
    return sum(nwalls)

print(brickwall(9,3))   #8
print(brickwall(9,4))   #10
print(brickwall(18,5))  #7958
print(brickwall(32,10)) #806844323190414