Ich könnte die Wiederholungsbeziehung nicht auf eine Frage wie unten schreiben.
Bei einem rechteckigen Gitter mit den Abmessungen 4 x n, wie viele Möglichkeiten gibt es, das Gitter komplett mit 2 x 2 und 2 x 1 Dominos zu kacheln?
Hier für 2 x 1 Rechtecke ist es sehr gut, aber ich konnte nicht herausfinden, ob Rechtecke 2 x 1 und 2 x 2 sind: http://www.acmgnyr.org/year2007/h.c
Irgendwelche Ideen?
Zum Beispiel für
4x1: 1 Weg
4x2: 11 Wege
4x3: 29 Wege
Code unten generiert alle Möglichkeiten mit Brute-Force. Aber ich möchte es mit dynamischer Programmierung machen.
https://gist.github.com/4519601
Antworten:
2 für die Antwort № 1Ich denke, dass Sie das mit einem dynamischen Programmieralgorithmus lösen können.
Stellen Sie sich vor, Sie würden das Gitter nicht als 4 x n Gitter darstellenvon Quadraten, aber als ein 4-Tupel, das die Breiten jeder einzelnen Spalte darstellt. Jedes Mal, wenn Sie eine Kachel platzieren, können Sie versuchen, sie so anzuordnen, dass eines ihrer Quadrate die linke obere Ecke der äußersten linken Seite des Rasters berührt. Dies bewirkt, dass die effektiven Breiten jeder der Spalten geändert werden. Zum Beispiel, angesichts dieses 4 x 3 Gitters:
. . .
. . .
. . .
. . .
Wir würden es als (3, 3, 3, 3) kodieren. Wenn du einen 2 x 2 Block in der oberen Ecke platzierst, bekommst du folgendes:
X X .
X X .
. . .
. . .
Dies würde als (1, 1, 3, 3) codiert werden, da die oberen zwei Zeilen nun effektiv viel kleiner sind.
Dies deutet auf eine anfängliche (ineffiziente) Rekursivität hinAlgorithmus. Als Ihre Basisfälle hat die Welt (0, 0, 0, 0) nur eine Lösung (nämlich nichts tun). Jede Welt, in der es keinen legalen Weg gibt, eine Kachel zu platzieren, die das oberste Quadrat der linken Reihe abdeckt, hat keine Lösung. Führe andernfalls für alle möglichen Züge diese Bewegung aus, aktualisiere die interne Darstellung der Welt und füge rekursiv alle Lösungen hinzu, die du in dieser kleineren Welt finden kannst.
Dies ist extrem langsam (exponentiell), kann aber dramatisch beschleunigt werden. Beachten Sie insbesondere, dass die Anzahl der möglichen 4-Tupel (n + 1) ist4. Dies bedeutet, dass die maximale Anzahl eindeutiger rekursiver Aufrufe O (n4). Wenn Sie also Ihre rekursiven Aufrufe memotisieren oder die dynamische Programmierung verwenden, um die Aufrufe rückwärts zu berechnen, müssen Sie nur eine polynomische Anzahl von Aufrufen erstellen. Memoization sollte sehr einfach zu einer vorhandenen rekursiven Lösung hinzugefügt werden, und die Beschleunigung sollte ziemlich enorm sein.
Wenn Sie mathematisch mehr suchenUm dieses Problem zu lösen, sollten Sie versuchen, eine generierende Funktion für dieses Problem zu schreiben und daraus eine Lösung in geschlossener Form abzuleiten. Sobald Sie das haben, sollte es nicht so schwer sein, es direkt viel effizienter zu bewerten als die obige Lösung. Da ich aber kein Experte bin, um Funktionen zu generieren, bin ich mir nicht sicher, wie Sie das machen würden .
Hoffe das hilft!
0 für die Antwort № 2
Im 4xn, n ist entweder gerade oder ungerade. ob n ist gerade, nur benutzen 2x2 Domino. Ansonsten, verwenden Sie 2x2 bis zu n-1. Dann benutze zwei 2x1 Dominosteine zum Abschluss 4x1 verbleibender Block. Bei der Beantwortung habe ich Ihrem Link nicht gefolgt, da ich davon ausgehe, dass die Frage ausreichend beantwortet ist und der Link einfach Ihre Antwort auf ein einfacheres Problem ist.
n = gerade
use n 2x2 dominoes
n = ungerade
use n-1 2x2 dominoes plus 2 2x1 domino
wenn n = 10, dann 4 · 10 = 40 und (2x2) · 10 = 40
wenn n = 11, dann 4 * 11 = 44 und (2x2) * 10 = 40 und (2x1) * 2 = 4 für insgesamt 44