Domanda
La domanda è da DP Piastrellatura di una piastrella 2xN con piastrelle a forma di L e piastrelle 2x1? Voglio una spiegazione su questa domanda o teoria
Soluzione
https://cs.stackexchange.com/questions/126237
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian ┌───────────┐
2 │ │
└───────────┘
m
m+1 m
┌─────────────┐ ┌───────────┐
2 │ ┌─┘ 2 │ └─┐
└───────────┘ └─────────────┘
m m+1
Per trovare la relazione di ricorrenza, provare a coprire lo spazio sul limite più a destra delle forme di cui sopra in tutti i modi possibili.
Considerare $ f [m] $ . Abbiamo i seguenti 4 modi per coprire lo spazio più a destra.
┌─────────┬─┐ ┌──────┬────┐ ┌───────┬───┐ ┌─────────┬─┐
│ │ │ │ ├────┤ │ └─┐ │ │ ┌─┘ │
└─────────┴─┘ └──────┴────┘ └─────────┴─┘ └───────┴───┘
What is left: (m-1)x2 (m-2)x2 (m-2)x2+1 (m-2)x2+1
Quindi, abbiamo $ \ quad \ quad f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ per $ m \ ge2 $ .
Considerare $ G [m] $ . Abbiamo i seguenti 2 modi per coprire lo spazio più a destra della prima forma.
m+1 m+1
┌─────────┬───┐ ┌─────────┬───┐
│ │ ┌─┘ │ └─┬─┘
└─────────┴─┘ └───────────┘
What is left: (m-1)x2 (m-1)x2+1
Quindi abbiamo $ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ per $ m \ Ge1 $ .
Applicazione delle due equazioni di recidiva di cui sopra, possiamo calcolare tutto $ f [m] $ e $ g [m] $ , in ordine crescente $ m $ , a partire da $ m= 2 $ , Data le condizioni iniziali, $ f [0]= 1 $ , $ f [1]= 1 $ , $ G [0]= 0 $ e $ g [1]= 1 $ .
Qui è un modo per ricavare una relazione di ricorrenza più semplice che coinvolge $ f $ solo.
La risposta di GloRfindel spiega come calcolare il numero di modelli "Taglia il blocco elementare più a destra". Per riepilogare, ci sono un blocco elementare di dimensioni $ 1 \ volte2 $ , un blocco elementare di $ 2 \ volte2 $ e due blocchi elementari di $ n \ times2 $ per $ n \ ge3 $ . Let $ f (n) $ essere il numero di modelli per $ 2 \ volte n $ . Abbiamo i seguenti casi di base e la relazione di ricorrenza, $$ f (0)= 1, \ f (1)= 1, \ f (2)= 2, $$ $$ f (n)= f (n-1) + f (n-2) + 2f (N-3) + 2F (N-4) + \ Cdots + 2F ( 0), \ testo {per} n \ ge3 $$
Le formule sopra riportate portano ad un algoritmo che calcola $ f (n) $ con $ o (n ^ 2) $ complessità del tempo e $ o (n) $ complessità spaziale.
Possiamo fare meglio. Sostituzione $ N $ con $ N-1 $ , abbiamo $$ F (N-1)= F (N-2) + F (N-3) + 2F (N-4) + 2F (N-5) + \ Cdots + 2F (0), \ testo {per} n \ ge4 $$
sottraendo le due equazioni di cui sopra, otteniamo $$ f (n) -f (n-1)= f (n-1) + f (n-3) $$ Quindi abbiamo per $ n \ ge4 $ , $$ f (n)= 2F (n-1) + f (n-3) \ tag {semplice} $$ Dal momento che $ f (3)= 5= 2f (2) + f (0) $ , la relazione di ricorrenza sopra riportata per tutte le $ n \ Ge3 $ . Questo porta ad un algoritmo che calcola $ f (n) $ con $ o (n) $ Complessità e $ o (1) $ spazio-complessità.
# Python program to compute the first n+1 values of f
def show_number_of_ways(n):
f = [0] * (n+1)
f[0] = f[1] = 1
f[2] = 2
for i in range(3, n+1):
f[i] = 2 * f[i - 1] + f[i - 3]
print(f)
show_number_of_ways(10)
# [1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255]
Possiamo anche trarre la semplice relazione di ricorrenza direttamente dalle prime due relazioni reciproche ricorsive tra $ f $ e $ g $ .
L'uguaglianza $ g [m]= f [m - 1] + g [m-1] $ ci dice $ f [m-1]= g [m] -g [m-1] $ , e, quindi, $ f [m]= g [m + 1] -G [m] $ e $ f [m-2]= g [m-1] -g [m-2] $ . Applicandoli per eliminare $ f $ lontano in $ f [m]= f [m - 1] + f [m - 1] 2] + G [m - 2] \ clot 2 $ , otteniamo $ g [m + 1]= 2g [m] + g [m-2] $ .
poiché $ f [m] $ è una combinazione lineare di $ g [m + 1] $ e $ G [m] $ , $ f $ soddisfaci
es lo stesso tipo di relazione di ricorrenza, I.e., $ f [m]= 2f [m-1] + f [M-3] $ .Controllo dell'intervallo valido dell'Indice $ M $ , vediamo che è valore per tutte le $ m \ ge3 $ .Altri suggerimenti
Un modo per pensarci sarebbe blocchi elementari, cioè blocchi che non possono essere divisi tagliandoli verticalmente.
Ora, una classe
In questo modo, puoi lavorare fino a 10x2.
Dopo aver calcolato alcuni termini, ho trovato la sequenza A052980 nell'enciclopedia on-line delle sequenze interi :
.A (N) è il numero di possibili tiling di una tavola da 2 x n, utilizzando Dominos e Tromini a forma di L. - Michael Tulskikh, 21 ago 2019
Quindi la risposta finale è 1255 per $ n= 10 $ .
