Let \(W(w,h)\) denote the number of walls of width \(w\) and height \(h\) built from horizontal bricks of lengths 2 and 3. Problem 215 asks for \(W(32,10)\). Every brick joint inside a row creates a vertical crack position somewhere in \(\{1,2,\dots,w-1\}\), and the wall is considered crack-free only when these interior joints never continue from one layer into the next.
The essential simplification is that the legality of a new row depends only on the crack pattern of the row immediately below it. Once each possible row is encoded, the two-dimensional wall becomes a finite-state counting problem on a compatibility graph.
The implementations do not reason about individual bricks after the row-generation stage. They work with row states, compatibility between states, and a recurrence over the wall height.
A single row is an ordered sum
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$$
So a valid row is exactly a composition of \(w\) using parts 2 and 3. If \(R(w)\) is the number of such rows, then the first brick is either 2 or 3, which gives the recurrence
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$$
For the target width \(32\), this yields \(R(32)=3329\) distinct row types. The code generates them by depth-first search rather than by evaluating the recurrence directly, but both viewpoints describe the same state space.
For a row \(b_1,\dots,b_t\), its internal crack set is
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$$
These partial sums are the only geometric information that matters once the row has been built.
A crack can propagate upward only if the row above and the row below both have a joint at the same horizontal position. Therefore the standard crack-free condition is enforced by requiring every pair of neighboring rows to have disjoint internal crack sets. In symbols, rows \(r\) and \(s\) may be stacked only when
$$C(r)\cap C(s)=\varnothing.$$
This local rule is exactly what the implementations test. It replaces the geometry of the whole wall by a pairwise invariant on consecutive rows.
The code stores a row by a bitmask rather than by an explicit set. If bit \(x\) is 1, then there is a crack at position \(x\). Equivalently,
$$m(r)=\sum_{x\in C(r)}2^x.$$
Two rows are compatible precisely when they have no common set bit:
$$m(r)\mathbin{\&}m(s)=0.$$
This turns the collection of rows into a graph: each row type is a vertex, and an edge joins two vertices exactly when the corresponding rows may appear consecutively in the wall.
Let \(F_h(i)\) be the number of crack-free walls of height \(h\) whose top row is the \(i\)-th row state. The first row can be chosen freely, so
$$F_1(i)=1.$$
For each additional layer, the new top row must be compatible with the previous top row, hence
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2),$$
where \(j\sim i\) means that row states \(j\) and \(i\) are compatible. The final count is
$$W(w,h)=\sum_i F_h(i).$$
Equivalently, if \(A\) is the adjacency matrix of the compatibility graph and \(\mathbf{1}\) is the all-ones vector, then
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1},$$
but the implementations evaluate this by iterative dynamic programming, not by matrix exponentiation.
For width \(9\), the possible rows are
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
Their crack sets are
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$$
Checking intersections shows that the only compatible pairs are
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$$
At height 1, every row contributes 1. At height 2, the state counts are just the vertex degrees: \(1,1,1,1,2\). Applying the recurrence once more gives height-3 counts \(1,2,2,1,2\), whose sum is
$$W(9,3)=8.$$
This is exactly the checkpoint used in the implementations, and it shows concretely how the graph recurrence replaces brute-force wall construction.
The C++, Python, and Java implementations recursively advance a cursor from the left end of the row. Each recursive step adds either a length-2 brick or a length-3 brick. Whenever a brick ends before the right boundary, the corresponding crack bit is set in the row mask. Reaching position \(32\) emits one complete row state.
Once all row masks have been generated, the implementation tests every pair of states. A pair is stored as compatible if their bitwise AND is zero. This produces an adjacency list for the compatibility graph, so the dynamic program does not need to repeat the crack test for every layer.
The DP starts with one way to end at each row state when the wall has height 1. For each of the remaining 9 layers, a new array is filled by summing the counts of all compatible predecessor states. Only the previous layer and the next layer are kept, so the memory usage stays linear in the number of row states rather than growing with the height.
Let \(N=R(w)\) be the number of row states and let \(E\) be the number of stored compatible transitions. Generating the rows visits each valid composition once, so it is \(O(N)\) up to small constant factors. Building the compatibility lists by testing every pair of row masks is \(O(N^2)\).
The height DP performs one sum over all compatible transitions for each extra layer, so its cost is \(O(hE)\). In the worst case this is \(O(hN^2)\), although the actual graph is much sparser than a complete graph. The memory footprint is \(O(N+E)\): the row masks, the adjacency structure, and two DP layers. For the target width \(32\), the main one-time burden is the compatibility graph on \(3329\) row states; the height \(10\) recurrence itself is then straightforward.
Sei \(W(w,h)\) die Anzahl der Wände der Breite \(w\) und Höhe \(h\), die aus horizontalen Steinen der Längen 2 und 3 aufgebaut werden. In Problem 215 ist \(W(32,10)\) gesucht. Jede innere Stoßstelle in einer Zeile erzeugt eine potenzielle vertikale Rissposition in \(\{1,2,\dots,w-1\}\), und die Wand gilt nur dann als rissfrei, wenn sich solche inneren Fugen nicht von einer Schicht in die nächste fortsetzen.
Der entscheidende Punkt ist, dass die Zulässigkeit einer neuen Zeile nur vom Fugenmuster der direkt darunterliegenden Zeile abhängt. Sobald man alle möglichen Zeilen codiert hat, wird die geometrische Aufgabe zu einem endlichen Zustandsgraphen mit einer einfachen Rekursion über die Höhe.
Nach dem Erzeugen der Zeilen arbeiten die Implementierungen nicht mehr mit einzelnen Steinen, sondern nur noch mit Zeilenzuständen, Verträglichkeit zwischen Zuständen und einem DP über die Höhe.
Eine einzelne Zeile ist eine geordnete Summe
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$$
Eine gültige Zeile ist also genau eine Komposition von \(w\) mit Teilen 2 und 3. Bezeichnet \(R(w)\) die Anzahl solcher Zeilen, dann liefert die Wahl des ersten Steins die Rekursion
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$$
Für die Zielbreite \(32\) ergibt das \(R(32)=3329\) verschiedene Zeilentypen. Der Code erzeugt sie per Tiefensuche; mathematisch ist es derselbe Zustandsraum.
Für eine Zeile \(b_1,\dots,b_t\) ist die Menge ihrer inneren Risspositionen
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$$
Diese Partialsummen sind nach der Konstruktion der Zeile die einzig relevante Information.
Ein Riss kann sich nur dann nach oben fortsetzen, wenn sowohl die untere als auch die obere Nachbarzeile an derselben horizontalen Position eine Fuge haben. Deshalb erzwingt man die Rissfreiheit, indem man für jedes benachbarte Zeilenpaar disjunkte innere Rissmengen verlangt. Zwei Zeilen \(r\) und \(s\) dürfen also nur dann übereinander stehen, wenn
$$C(r)\cap C(s)=\varnothing.$$
Genau diese lokale Bedingung prüfen die Implementierungen. Dadurch wird eine globale geometrische Forderung auf ein paarweises Invariante reduziert.
Im Code wird eine Zeile nicht als explizite Menge, sondern als Bitmaske gespeichert. Ist Bit \(x\) gesetzt, dann gibt es an Position \(x\) eine Fuge. Äquivalent dazu gilt
$$m(r)=\sum_{x\in C(r)}2^x.$$
Zwei Zeilen sind genau dann verträglich, wenn sie kein gemeinsames gesetztes Bit besitzen:
$$m(r)\mathbin{\&}m(s)=0.$$
Damit entsteht ein Graph: Jeder Zeilentyp ist ein Knoten, und eine Kante verbindet genau die Zeilen, die aufeinander folgen dürfen.
Sei \(F_h(i)\) die Anzahl rissfreier Wände der Höhe \(h\), deren oberste Zeile der \(i\)-te Zustand ist. Die erste Zeile ist frei wählbar, also
$$F_1(i)=1.$$
Für jede weitere Schicht muss die neue Oberzeile mit der bisherigen Oberzeile verträglich sein, daher
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2).$$
Die Gesamtzahl lautet
$$W(w,h)=\sum_i F_h(i).$$
Mit der Adjazenzmatrix \(A\) des Verträglichkeitsgraphen kann man das auch als
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1}$$
schreiben; die Implementierungen berechnen dies aber iterativ per DP und nicht mittels Matrixpotenzen.
Für Breite \(9\) gibt es genau die Zeilen
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
Ihre Rissmengen sind
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$$
Aus den Schnittmengen sieht man, dass nur die Paare
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}$$
verträglich sind. In Höhe 1 trägt jede Zeile den Wert 1. In Höhe 2 erhält man daher einfach die Knotengrade \(1,1,1,1,2\). Noch ein Rekursionsschritt liefert für Höhe 3 die Werte \(1,2,2,1,2\), also insgesamt
$$W(9,3)=8.$$
Genau diesen Kontrollwert verwenden die Implementierungen, und er zeigt anschaulich, wie die Graphrekursion die naive Wandkonstruktion ersetzt.
Die Implementierungen in C++, Python und Java schieben rekursiv einen Positionszeiger von links nach rechts. Jeder Schritt setzt entweder einen 2er- oder einen 3er-Stein. Endet ein Stein vor dem rechten Rand, wird das passende Riss-Bit in der Maske gesetzt. Sobald Position \(32\) erreicht ist, liegt ein vollständiger Zeilenzustand vor.
Nach der Erzeugung aller Bitmasken testet die Implementierung jedes Zustandspaar. Ist das bitweise UND null, wird das Paar als kompatibel gespeichert. So entsteht eine Adjazenzliste des Verträglichkeitsgraphen, und der DP-Schritt muss die Rissbedingung nicht in jeder Höhe neu auswerten.
Der DP-Vektor startet mit einem Eintrag 1 für jeden Zeilenzustand bei Höhe 1. Für jede der verbleibenden 9 Schichten wird ein neuer Vektor gefüllt, indem man die Werte aller kompatiblen Vorgänger aufsummiert. Es werden immer nur die vorige und die nächste Schicht gehalten, daher bleibt der Speicher linear in der Zahl der Zustände.
Sei \(N=R(w)\) die Anzahl der Zeilenzustände und \(E\) die Anzahl der gespeicherten kompatiblen Übergänge. Das Erzeugen der Zeilen besucht jede gültige Komposition genau einmal und ist damit bis auf kleine Konstanten \(O(N)\). Der Aufbau der Kompatibilitätslisten durch Test aller Paare kostet \(O(N^2)\).
Das Höhen-DP summiert für jede zusätzliche Schicht über alle kompatiblen Übergänge und benötigt daher \(O(hE)\). Im Worst Case ist das \(O(hN^2)\), tatsächlich ist der Graph aber deutlich dünner als vollständig. Der Speicherbedarf ist \(O(N+E)\): Bitmasken, Adjazenzstruktur und zwei DP-Ebenen. Für die Zielbreite \(32\) ist die einmalige Hauptarbeit also der Verträglichkeitsgraph auf \(3329\) Zeilenzuständen; die Rekursion bis Höhe \(10\) ist danach direkt.
\(W(w,h)\), yatay yerleştirilmiş uzunlukları 2 ve 3 olan tuğlalarla örülen, genişliği \(w\) ve yüksekliği \(h\) olan duvarların sayısı olsun. Problem 215, \(W(32,10)\) değerini sorar. Bir satır içindeki her iç birleşim noktası \(\{1,2,\dots,w-1\}\) kümesinde bir dikey çatlak konumu üretir ve duvar ancak bu iç derzler bir alttaki satırla hizalanmadığında crack-free kabul edilir.
Asıl kolaylaştırıcı nokta şudur: yeni bir satırın yerleştirilebilir olup olmaması yalnızca hemen altındaki satırın derz düzenine bağlıdır. Bütün olası satırlar kodlandığında, iki boyutlu geometri sonlu durumlu bir uyumluluk grafına ve yükseklik boyunca akan bir sayma problemine dönüşür.
Satırlar üretildikten sonra uygulamalar artık tek tek tuğlalarla ilgilenmez. Hesaplama, satır durumları, bu durumlar arasındaki uyumluluk ve yükseklik boyunca kurulan bir DP üzerinden yürür.
Tek bir satır,
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}$$
şeklinde sıralı bir toplamdır. Yani geçerli bir satır, \(w\)'nin yalnızca 2 ve 3 parçalarıyla yazılmış bir bileşimidir. \(R(w)\) bu satırların sayısıysa, ilk tuğlanın 2 ya da 3 olmasına göre
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3)$$
elde edilir. Hedef genişlik \(32\) için bu sayı \(R(32)=3329\)'dur. Kod bunları doğrudan bu bağıntıyla değil, derinlik öncelikli aramayla üretir; ama üretilen durum uzayı aynıdır.
\(b_1,\dots,b_t\) satırının iç çatlak kümesi
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}$$
olarak tanımlanır. Satır kurulduktan sonra önemli olan tek geometrik veri bu kısmi toplamların kümesidir.
Bir çatlak ancak üst satır ile alt satır aynı yatay konumda derz taşıyorsa yukarı doğru devam edebilir. Bu yüzden crack-free koşulu, her komşu satır çiftinin iç çatlak kümelerinin ayrık olmasını istemekle sağlanır. Yani \(r\) ve \(s\) satırları ancak
$$C(r)\cap C(s)=\varnothing$$
ise üst üste gelebilir. Uygulamaların test ettiği yerel invariant tam olarak budur; böylece tüm duvara ait geometrik koşul, ardışık satırlar arasındaki ikili bir kurala indirgenir.
Kod, çatlak kümelerini açıkça saklamak yerine satırı bir bitmask ile temsil eder. Bit \(x\) açıksa, \(x\) konumunda bir derz vardır. Eşdeğer olarak
$$m(r)=\sum_{x\in C(r)}2^x$$
yazılabilir. İki satır ancak ortak açık bit taşımıyorsa uyumludur:
$$m(r)\mathbin{\&}m(s)=0.$$
Böylece her satır tipini bir düğüm kabul edip, yalnızca birlikte gelebilen satırlar arasında kenar bulunan bir uyumluluk grafı elde ederiz.
\(F_h(i)\), yüksekliği \(h\) olan ve en üst satırı \(i\). durum olan crack-free duvarların sayısı olsun. İlk satır serbesttir, dolayısıyla
$$F_1(i)=1.$$
Her yeni katmanda üstteki satırın bir önceki üst satırla uyumlu olması gerekir; bu da
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2)$$
bağıntısını verir. Aranan toplam değer
$$W(w,h)=\sum_i F_h(i)$$
olur. İstenirse bu, uyumluluk grafının komşuluk matrisi \(A\) ile
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1}$$
şeklinde de yazılabilir; fakat uygulamalar matris üssü almak yerine bu ilişkiyi doğrudan DP ile değerlendirir.
Genişlik \(9\) için mümkün satırlar şunlardır:
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
Bunların çatlak kümeleri
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}$$
olur. Kesişimleri kontrol edince yalnızca şu çiftlerin uyumlu olduğu görülür:
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$$
Yükseklik 1'de bütün satırların değeri 1'dir. Yükseklik 2'de durum sayıları düğüm derecelerine eşit olur: \(1,1,1,1,2\). Bağıntıyı bir kez daha uygularsak yükseklik 3 için \(1,2,2,1,2\) elde edilir ve toplam
$$W(9,3)=8$$
çıkar. Uygulamalardaki kontrol örneği tam olarak budur; ayrıca graf tabanlı DP'nin neden yeterli olduğunu somut biçimde gösterir.
C++, Python ve Java uygulamaları soldan başlayan bir konumu özyinelemeli olarak ilerletir. Her adımda ya 2 uzunluklu ya da 3 uzunluklu bir tuğla eklenir. Tuğla sağ sınıra gelmeden biterse ilgili çatlak biti maskede açılır. Konum \(32\)'ye ulaştığında tek bir tamamlanmış satır durumu elde edilmiş olur.
Bütün maskeler üretildikten sonra uygulama her durum çiftini test eder. Bitwise AND sonucu sıfırsa bu iki durum uyumlu olarak saklanır. Böylece uyumluluk grafının komşuluk listeleri hazırlanır ve yükseklik DP'si sırasında aynı çatlak testi tekrar tekrar yapılmaz.
DP vektörü, yükseklik 1 için her satır durumu adına 1 ile başlar. Kalan 9 katmanın her biri için yeni bir dizi oluşturulur ve her duruma gelebilen uyumlu öncüllerin sayıları toplanır. Sadece önceki ve sonraki katman tutulduğu için bellek, yükseklikle değil durum sayısıyla orantılı kalır.
\(N=R(w)\) satır durumu sayısı ve \(E\) saklanan uyumlu geçiş sayısı olsun. Satır üretimi her geçerli bileşimi bir kez ziyaret ettiği için küçük sabitlerle \(O(N)\) maliyetlidir. Tüm çiftlerin test edilmesiyle uyumluluk listelerinin kurulması ise \(O(N^2)\) zaman alır.
Yükseklik DP'si her ek katmanda tüm uyumlu geçişler üzerinden toplam aldığı için \(O(hE)\) maliyetlidir. En kötü durumda bu \(O(hN^2)\) olur, fakat gerçek graf tam graf olmaktan çok uzaktır. Bellek kullanımı \(O(N+E)\)'dir: satır maskeleri, komşuluk yapısı ve iki DP katmanı. Hedef genişlik \(32\) için asıl tek seferlik yük, \(3329\) durumlu uyumluluk grafını kurmaktır; yükseklik \(10\) için yapılan DP bundan sonra doğrudandır.
Sea \(W(w,h)\) el número de muros de anchura \(w\) y altura \(h\) construidos con ladrillos horizontales de longitudes 2 y 3. El Problema 215 pide \(W(32,10)\). Cada junta interior de una fila crea una posible posición de grieta vertical en \(\{1,2,\dots,w-1\}\), y el muro solo se considera libre de grietas cuando esas juntas interiores no continúan de una capa a la siguiente.
La simplificación clave es que la legalidad de una fila nueva depende únicamente del patrón de juntas de la fila inmediatamente inferior. Una vez codificadas todas las filas posibles, la geometría del muro se convierte en un problema finito de conteo sobre un grafo de compatibilidad.
Después de generar las filas, las implementaciones ya no trabajan ladrillo por ladrillo. Todo se reduce a estados de fila, compatibilidad entre esos estados y una recurrencia sobre la altura.
Una fila individual es una suma ordenada
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$$
Por tanto, una fila válida es exactamente una composición de \(w\) usando partes 2 y 3. Si \(R(w)\) denota el número de esas filas, elegir el primer ladrillo produce
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$$
Para la anchura objetivo \(32\), esto da \(R(32)=3329\) tipos distintos de fila. El código los genera por búsqueda en profundidad, pero matemáticamente se trata del mismo espacio de estados.
Para una fila \(b_1,\dots,b_t\), su conjunto de grietas internas es
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$$
Esas sumas parciales son la única información geométrica relevante una vez construida la fila.
Una grieta solo puede prolongarse hacia arriba si la fila inferior y la fila superior tienen una junta en la misma posición horizontal. Por eso la condición crack-free se impone exigiendo que cada par de filas vecinas tenga conjuntos de grietas internas disjuntos. Es decir, las filas \(r\) y \(s\) solo pueden apilarse si
$$C(r)\cap C(s)=\varnothing.$$
Esa es exactamente la condición local que verifican las implementaciones. Así, una restricción geométrica global se reemplaza por un invariante binario entre filas consecutivas.
El código no guarda una fila como conjunto explícito, sino como una máscara de bits. Si el bit \(x\) vale 1, existe una junta en la posición \(x\). De forma equivalente,
$$m(r)=\sum_{x\in C(r)}2^x.$$
Dos filas son compatibles exactamente cuando no comparten ningún bit activo:
$$m(r)\mathbin{\&}m(s)=0.$$
Esto convierte el problema en un grafo: cada tipo de fila es un vértice y dos vértices se unen cuando las filas correspondientes pueden aparecer en capas consecutivas.
Sea \(F_h(i)\) el número de muros crack-free de altura \(h\) cuya fila superior es el estado \(i\). La primera fila puede elegirse libremente, así que
$$F_1(i)=1.$$
Cada nueva capa debe ser compatible con la fila superior anterior, por lo que
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2).$$
El total buscado es
$$W(w,h)=\sum_i F_h(i).$$
También puede escribirse, usando la matriz de adyacencia \(A\), como
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1},$$
aunque las implementaciones evalúan esta fórmula mediante programación dinámica iterativa y no con exponenciación de matrices.
Para anchura \(9\), las filas posibles son
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
Sus conjuntos de grietas son
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$$
Al comprobar intersecciones, los únicos pares compatibles son
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$$
En altura 1, cada fila aporta 1. En altura 2, las cuentas por estado son simplemente los grados \(1,1,1,1,2\). Una aplicación más de la recurrencia produce para altura 3 los valores \(1,2,2,1,2\), cuya suma es
$$W(9,3)=8.$$
Ese es exactamente el punto de control usado en las implementaciones, y muestra con claridad cómo la recurrencia en el grafo sustituye la construcción exhaustiva de muros.
Las implementaciones en C++, Python y Java avanzan recursivamente un cursor desde el extremo izquierdo de la fila. En cada paso añaden un ladrillo de longitud 2 o 3. Si el ladrillo termina antes del borde derecho, se activa en la máscara el bit correspondiente a esa junta. Cuando la posición alcanza \(32\), se ha generado un estado completo de fila.
Una vez generadas todas las máscaras, la implementación prueba cada par de estados. Si el AND bit a bit es cero, el par se almacena como compatible. Así se obtiene una lista de adyacencia para el grafo de compatibilidad y la condición de grietas no necesita reevaluarse en cada capa.
El vector DP empieza con valor 1 para cada estado cuando la altura es 1. En cada una de las 9 capas restantes, se llena un nuevo vector sumando los conteos de todos los predecesores compatibles. Solo se guardan la capa anterior y la siguiente, de modo que la memoria permanece lineal en el número de estados.
Sea \(N=R(w)\) el número de estados de fila y \(E\) el número de transiciones compatibles almacenadas. Generar las filas visita cada composición válida una sola vez, así que cuesta \(O(N)\) salvo factores constantes pequeños. Construir las listas de compatibilidad probando todos los pares cuesta \(O(N^2)\).
El DP en altura realiza una suma sobre todas las transiciones compatibles por cada capa adicional, por lo que cuesta \(O(hE)\). En el peor caso eso sería \(O(hN^2)\), aunque el grafo real es bastante más disperso que un grafo completo. La memoria es \(O(N+E)\): máscaras de fila, estructura de adyacencia y dos capas del DP. Para la anchura objetivo \(32\), el trabajo dominante de una sola vez es construir el grafo de compatibilidad sobre \(3329\) estados; después, la recurrencia hasta altura \(10\) es directa.
记 \(W(w,h)\) 为用长度 2 和 3 的水平砖块砌成、宽度为 \(w\)、高度为 \(h\) 的墙的数量。第 215 题要求的是 \(W(32,10)\)。每一层内部的砖缝都会在 \(\{1,2,\dots,w-1\}\) 中产生一个潜在的竖向裂缝位置，而所谓 crack-free，正是要求这些内部接缝不能从一层延续到它正上方的那一层。
真正的简化来自一个局部性事实：能否再放一层，只取决于紧挨着它下方那一层的接缝分布。只要把所有可能的单层编码出来，整面墙的问题就会变成一个有限状态的兼容图计数问题。
代码在生成完单层之后，就不再逐块处理砖头了。后续计算完全建立在“层状态”“状态之间是否兼容”以及“沿高度方向的递推”这三个对象上。
单独一层可以写成
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$$
也就是说，一层的合法铺法恰好是把 \(w\) 写成若干个 2 和 3 的有序和。如果 \(R(w)\) 表示这样的行数，那么按第一块砖的长度分类，立刻得到
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$$
对于目标宽度 \(32\)，因此共有 \(R(32)=3329\) 种不同的单层状态。程序没有显式按这个递推表去算，而是用深度优先搜索把所有铺法枚举出来；但从数学上说，它们描述的是同一个状态空间。
若一层写成 \(b_1,\dots,b_t\)，那么它的内部接缝集合就是
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$$
这些前缀和完全决定了这一层与其他层之间是否会形成裂缝延续，所以一旦行已经生成，后面只需要关心这个集合。
一条竖向裂缝要想继续向上延伸，必要条件是上下两层在同一个水平位置都出现接缝。因此，题目要求的 crack-free 条件，可以通过一个局部规则来保证：任何相邻两层都不能在同一内部位置同时出现接缝。也就是说，行 \(r\) 与行 \(s\) 只有在
$$C(r)\cap C(s)=\varnothing$$
时才允许相邻出现。实现程序检查的正是这个条件。这样一来，“整面墙是否安全”这个全局几何条件就被压缩成了相邻两层之间的二元约束。
程序并不把接缝保存成显式集合，而是把一层编码成一个位掩码：如果第 \(x\) 位为 1，表示在位置 \(x\) 有一条内部接缝。等价地，
$$m(r)=\sum_{x\in C(r)}2^x.$$
两层兼容，当且仅当它们没有共同置位：
$$m(r)\mathbin{\&}m(s)=0.$$
于是问题自然变成一个图：每一种行状态是一个顶点，如果两行可以上下相邻，就在它们之间连一条边。
设 \(F_h(i)\) 表示高度为 \(h\) 且最上层是第 \(i\) 个行状态的 crack-free 墙数量。第一层可以任意选，所以
$$F_1(i)=1.$$
再往上放一层时，新顶层必须与旧顶层兼容，因此有
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2),$$
其中 \(j\sim i\) 表示两种行状态兼容。最终答案就是
$$W(w,h)=\sum_i F_h(i).$$
如果把兼容图的邻接矩阵记为 \(A\)，这个式子也可以写成
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1},$$
不过实现并没有真的去做矩阵快速幂，而是直接反复应用上面的状态转移。
宽度 \(9\) 时，所有可能的单层恰好是
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
对应的接缝集合分别为
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$$
逐一检查交集后可以发现，只有下面三类配对兼容：
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$$
高度为 1 时，每个状态的计数都是 1。高度为 2 时，各状态计数就是图中的度数，即 \(1,1,1,1,2\)。再应用一次递推，高度为 3 时变成 \(1,2,2,1,2\)，总和就是
$$W(9,3)=8.$$
这正是实现中用来校验逻辑的小例子，也非常直观地展示了：真正需要计数的不是“墙本身”，而是兼容图上的长度固定的路径。
C++、Python 和 Java 实现都会从一行的最左端开始递归推进一个位置指针。每一步添加一块长度为 2 或 3 的砖；如果这块砖在右边界之前结束，就把对应位置的接缝位写入掩码。当位置恰好到达 \(32\) 时，就得到一个完整的行状态。
所有位掩码生成后，程序会检查每一对行状态。若两者按位与为零，就把这对状态记为兼容。这样得到的是兼容图的邻接表，因此在后续 DP 中不需要反复重新判断接缝是否重合。
DP 初始时把高度 1 的每个行状态都赋值为 1。接下来的 9 层中，每一层都新建一个数组，并把所有兼容前驱的计数累加到当前状态上。程序始终只保留“上一层”和“下一层”两个数组，因此空间复杂度保持在线性级别，而不会随着高度增长。
设 \(N=R(w)\) 是行状态数，\(E\) 是存储下来的兼容转移数。生成行状态时，每一种合法的有序分拆只会访问一次，因此在常数因子很小的前提下可视为 \(O(N)\)。枚举所有状态对并建立兼容表需要 \(O(N^2)\) 时间。
高度 DP 在每增加一层时都要沿所有兼容转移做一次求和，所以代价是 \(O(hE)\)。最坏情况下可写作 \(O(hN^2)\)，不过实际兼容图远比完全图稀疏。空间方面是 \(O(N+E)\)：行掩码、邻接结构以及两层 DP 数组。对于题目的目标宽度 \(32\)，真正一次性的主要工作量是构建 \(3329\) 个行状态之间的兼容图，之后高度 \(10\) 的递推就相当直接了。
Пусть \(W(w,h)\) обозначает число стен ширины \(w\) и высоты \(h\), сложенных из горизонтальных кирпичей длины 2 и 3. В задаче 215 требуется найти \(W(32,10)\). Каждая внутренняя граница между кирпичами в строке задает потенциальную вертикальную трещину в одной из позиций \(\{1,2,\dots,w-1\}\), и стена считается crack-free только тогда, когда такие внутренние швы не продолжаются из одного слоя в следующий.
Главное упрощение состоит в том, что допустимость новой строки определяется только рисунком швов в строке непосредственно под ней. Как только все возможные строки закодированы, геометрическая задача превращается в конечный подсчет путей в графе совместимости.
После этапа генерации строк реализации уже не думают о кирпичах по отдельности. Они работают со строковыми состояниями, совместимостью между ними и рекуррентным переходом по высоте стены.
Одна строка имеет вид
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$$
То есть допустимая строка есть в точности композиция числа \(w\) из частей 2 и 3. Если через \(R(w)\) обозначить число таких строк, то выбор первого кирпича дает рекурсию
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$$
Для целевой ширины \(32\) получаем \(R(32)=3329\) различных типов строк. В коде они порождаются поиском в глубину, но математически это тот же самый набор состояний.
Для строки \(b_1,\dots,b_t\) множество внутренних трещин равно
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$$
После построения строки именно эти частичные суммы полностью определяют, как она взаимодействует с соседними слоями.
Трещина может продолжиться вверх только в том случае, если и нижняя, и верхняя соседние строки имеют шов в одной и той же горизонтальной позиции. Поэтому условие crack-free реализуется локально: каждая пара соседних строк должна иметь непересекающиеся множества внутренних швов. Иными словами, строки \(r\) и \(s\) можно ставить друг над другом только если
$$C(r)\cap C(s)=\varnothing.$$
Именно это локальное условие проверяют реализации. Благодаря этому глобальное геометрическое требование заменяется простым инвариантом для соседних строк.
В программе строка хранится не как явное множество, а как битовая маска. Если бит \(x\) установлен, значит, в позиции \(x\) есть внутренний шов. Эквивалентно,
$$m(r)=\sum_{x\in C(r)}2^x.$$
Две строки совместимы тогда и только тогда, когда у них нет общих установленных битов:
$$m(r)\mathbin{\&}m(s)=0.$$
Тем самым возникает граф: каждая строка дает вершину, а ребро проводится между теми вершинами, чьи строки можно ставить подряд.
Пусть \(F_h(i)\) обозначает число crack-free стен высоты \(h\), у которых верхняя строка имеет состояние \(i\). Первая строка выбирается произвольно, поэтому
$$F_1(i)=1.$$
Каждый следующий слой должен быть совместим с предыдущим верхним слоем, значит
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2).$$
Окончательное число стен равно
$$W(w,h)=\sum_i F_h(i).$$
Если \(A\) — матрица смежности графа совместимости, то это же можно записать как
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1},$$
но реализации вычисляют эту формулу обычным итеративным DP, а не возведением матрицы в степень.
При ширине \(9\) возможны ровно следующие строки:
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
Их множества трещин таковы:
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$$
Проверка пересечений показывает, что совместимы только пары
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$$
На высоте 1 все состояния имеют значение 1. На высоте 2 получаются просто степени вершин: \(1,1,1,1,2\). Еще одно применение рекурсии дает для высоты 3 значения \(1,2,2,1,2\), и их сумма равна
$$W(9,3)=8.$$
Именно этот контрольный пример используют реализации, и он наглядно показывает, как задача о стенах сводится к подсчету путей в графе совместимости.
Реализации на C++, Python и Java рекурсивно двигают указатель позиции от левого края строки. На каждом шаге добавляется кирпич длины 2 или 3. Если кирпич заканчивается раньше правой границы, соответствующий бит шва устанавливается в маске. Когда позиция достигает \(32\), получается одно полное состояние строки.
После генерации всех масок программа проверяет каждую пару состояний. Если их побитовое AND равно нулю, пара сохраняется как совместимая. Так строится список смежности графа совместимости, и в фазе DP уже не нужно заново проверять пересечение швов.
Начальный DP-вектор присваивает значение 1 каждому состоянию при высоте 1. Для каждой из оставшихся 9 строк строится новый вектор, куда суммируются значения всех совместимых предшественников. Хранятся только предыдущий и следующий слои, поэтому память растет линейно по числу состояний, а не по высоте.
Пусть \(N=R(w)\) — число строковых состояний, а \(E\) — число сохраненных совместимых переходов. Генерация строк посещает каждую допустимую композицию ровно один раз, так что ее стоимость равна \(O(N)\) с малыми постоянными. Построение списков совместимости перебором всех пар занимает \(O(N^2)\).
DP по высоте на каждом дополнительном слое суммирует по всем совместимым переходам, следовательно, работает за \(O(hE)\). В худшем случае это \(O(hN^2)\), хотя реальный граф заметно разреженнее полного. Память составляет \(O(N+E)\): битовые маски строк, структура смежности и два слоя DP. Для целевой ширины \(32\) основной одноразовый расход времени — построение графа совместимости на \(3329\) состояниях, после чего переходы до высоты \(10\) уже тривиальны.
لنرمز بـ \(W(w,h)\) إلى عدد الجدران ذات العرض \(w\) والارتفاع \(h\) المبنية من طوب أفقي طوله 2 أو 3. المطلوب في المسألة 215 هو حساب \(W(32,10)\). كل فاصل داخلي بين طوبتين في صف واحد يحدد موضعًا محتملًا لشق رأسي ضمن المجموعة \(\{1,2,\dots,w-1\}\)، ويُعد الجدار crack-free فقط إذا لم يستمر هذا الفاصل الداخلي من طبقة إلى الطبقة التي تعلوها مباشرة.
التبسيط الحاسم هو أن صلاحية إضافة صف جديد تعتمد فقط على نمط الفواصل في الصف الموجود تحته مباشرة. وما إن نُرمّز جميع الصفوف الممكنة حتى تتحول المسألة الهندسية إلى مسألة عدّ على رسم بياني منتهٍ للحالات المتوافقة.
بعد توليد الصفوف، لا تعود الحلول تتعامل مع الطوب قطعةً قطعة. الحساب كله يُبنى على حالات الصفوف، وعلى علاقة التوافق بينها، وعلى علاقة رجعية تسير مع الارتفاع.
يمكن كتابة الصف الواحد على الصورة
$$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$$
أي إن الصف الصحيح هو تركيب مرتب للعدد \(w\) باستخدام الجزأين 2 و3 فقط. إذا رمزنا بعدد هذه الصفوف بـ \(R(w)\)، فإن اختيار أول طوبة يعطي العلاقة
$$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$$
وعند العرض \(32\) نحصل على \(R(32)=3329\) نمطًا مختلفًا للصفوف. الشيفرة تولد هذه الأنماط ببحث عمقي، لكن من الناحية الرياضية هذا هو فضاء الحالات نفسه.
إذا كان الصف هو \(b_1,\dots,b_t\)، فإن مجموعة مواضع الفواصل الداخلية فيه هي
$$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$$
هذه المجاميع الجزئية هي كل ما نحتاجه بعد بناء الصف، لأنها تحدد كيف يمكن لهذا الصف أن يجاور غيره.
لا يستطيع الشق أن يواصل امتداده إلى أعلى إلا إذا كان الصف السفلي والصف العلوي يملكان فاصلًا داخليًا عند الموضع الأفقي نفسه. لذلك تُفرض خاصية crack-free محليًا بأن نطلب من كل صفين متجاورين أن تكون مجموعتا الفواصل الداخلية فيهما منفصلتين. أي إن الصفين \(r\) و\(s\) يمكن أن يتراصا فقط إذا تحقق
$$C(r)\cap C(s)=\varnothing.$$
وهذا هو الشرط المحلي نفسه الذي تطبقه الحلول البرمجية. بذلك تتحول القيود الهندسية العالمية إلى ثابت بسيط بين كل صفين متتالين.
بدل حفظ مجموعة الفواصل صراحةً، تمثل الشيفرة الصف بقناع بتات. إذا كان البت \(x\) مساويًا لـ 1، فهذا يعني وجود فاصل عند الموضع \(x\). وبشكل مكافئ،
$$m(r)=\sum_{x\in C(r)}2^x.$$
ويكون صفان متوافقين إذا وفقط إذا لم يشتركا في أي بت مفعّل:
$$m(r)\mathbin{\&}m(s)=0.$$
ومن هنا ينشأ رسم بياني طبيعي: كل نمط صف هو عقدة، وتوجد حافة بين عقدتين إذا أمكن وضع الصفين الموافقين فوق بعضهما.
ليكن \(F_h(i)\) عدد الجدران crack-free ذات الارتفاع \(h\) والتي يكون صفها العلوي هو الحالة \(i\). بما أن الصف الأول يمكن اختياره بحرية، فإن
$$F_1(i)=1.$$
وعند إضافة طبقة جديدة يجب أن يكون الصف العلوي الجديد متوافقًا مع الصف الذي تحته، ولذلك
$$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2).$$
والعدد الكلي المطلوب هو
$$W(w,h)=\sum_i F_h(i).$$
ويمكن أيضًا كتابة ذلك باستخدام مصفوفة المجاورة \(A\) على الصورة
$$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1},$$
لكن التنفيذ لا يستخدم رفع المصفوفة لأس، بل يطبّق هذا الانتقال مباشرة بواسطة البرمجة الديناميكية التكرارية.
عند العرض \(9\) تكون الصفوف الممكنة هي
$$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$$
ومواضع الفواصل الداخلية المقابلة لها هي
$$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$$
وبفحص التقاطعات نجد أن الأزواج المتوافقة الوحيدة هي
$$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$$
عند الارتفاع 1 تكون قيمة كل حالة مساوية لـ 1. وعند الارتفاع 2 تصبح القيم هي درجات العقد نفسها: \(1,1,1,1,2\). وبعد تطبيق العلاقة الرجعية مرة أخرى نحصل عند الارتفاع 3 على \(1,2,2,1,2\)، ومن ثم
$$W(9,3)=8.$$
وهذه هي قيمة الفحص الصغيرة المستخدمة في الحلول، وهي توضح عمليًا كيف يحل عدّ المسارات في رسم التوافق محل البناء الشامل لكل الجدران الممكنة.
تقوم تطبيقات C++ وPython وJava بتحريك مؤشر موضع من يسار الصف إلى يمينه بطريقة عودية. وفي كل خطوة تُضاف طوبة بطول 2 أو 3. وإذا انتهت الطوبة قبل الحد الأيمن، يُفعَّل البت الموافق لموضع الفاصل في القناع. وعندما يصل الموضع إلى \(32\)، نحصل على حالة صف كاملة.
بعد توليد جميع الأقنعة، تفحص الشيفرة كل زوج من الحالات. فإذا كان AND على مستوى البتات يساوي صفرًا، يُخزن الزوج باعتباره متوافقًا. وبهذا تتشكل قوائم مجاورة للرسم البياني، فلا نحتاج إلى إعادة فحص الفواصل في كل طبقة أثناء DP.
تبدأ البرمجة الديناميكية بقيمة 1 لكل حالة عند الارتفاع 1. ولكل واحدة من الطبقات التسع المتبقية يُنشأ صف جديد من القيم عبر جمع أعداد جميع الأسلاف المتوافقين. ولا يُحفظ في الذاكرة إلا المستوى السابق والمستوى التالي، لذلك يبقى استهلاك الذاكرة خطيًا في عدد الحالات.
إذا كان \(N=R(w)\) هو عدد حالات الصفوف و\(E\) هو عدد الانتقالات المتوافقة المخزنة، فإن توليد الصفوف يزور كل تركيب صالح مرة واحدة، ولذلك كلفته \(O(N)\) مع ثوابت صغيرة. أما بناء قوائم التوافق عبر فحص كل الأزواج فيكلف \(O(N^2)\).
وتكلفة DP على الارتفاع هي \(O(hE)\)، لأن كل طبقة إضافية تجمع على جميع الانتقالات المتوافقة. وفي أسوأ الأحوال يمكن كتابتها \(O(hN^2)\)، مع أن الرسم الفعلي أكثر تخلخلًا بكثير من الرسم الكامل. الذاكرة هي \(O(N+E)\): أقنعة الصفوف، بنية المجاورة، وطبقتان من DP. وعند العرض المستهدف \(32\)، يكون العبء الرئيسي لمرة واحدة هو بناء رسم التوافق على \(3329\) حالة صف؛ وبعد ذلك يصبح الانتقال حتى الارتفاع \(10\) مباشرًا.