# mengisi tabel $2\times x$ dengan ubin berbentuk $2\times1$ dan ubin berbentuk L
###### tags: `dp`
Definisikan $f(x)$ sebagai banyaknya cara menyusun $2\times x$

kita punya 4 kasus:
1. 
berarti di kasus ini kita tinggal mengisi $2 \times (x-1)$ sehingga ada $f(x-1)$ cara
2. 
berarti di kasus ini kita tinggal mengisi $2 \times (x-2)$ sehingga ada $f(x-2)$ cara
3. 
definisikan kasus ini sebagai $g(x)$, maka banyaknya cara menyusunnya ada $g(x)$ cara
4. 
kasus ini merupakan kebalikan dari kasus 3 sehingga banyaknya cara menyusunnya ada $g(x)$ cara

sehingga $f(x)=f(x-1)+f(x-2)+2\times g(x)$

---
## mencari $g(x)$

kita punya dua kasus :
1. 
berarti menurut definisi $g(x)$, kasus ini ada $g(x-1)$ cara karena $2\times1$ paling kiri sudah terisi
2. 
berarti tersisa $2\times(x-3)$ yg harus diisi. sehingga ada kasus ini ada $f(x-3)$ cara

sehingga $g(x)=g(x-1)+f(x-3)$

---
## mencari **basecase**:
- ketika $x=0$, maka hanya ada satu cara yaitu tidak mengisi ubinnya. sehingga $f(0)=g(0)=1$
- ketika $x=1$, maka $f(1)=1$ karena $2\times1$ hanya bisa diisi oleh ubin $2\times1$ vertikal. sedangkan $g(1)=0$ karena kita tidak bisa mengisi $2\times1$ dengan ubin berbentuk **L**
- ketika $x=2$, maka $f(2)=2$ karena $2\times1$ hanya bisa diisi oleh ubin $2\times2$ secara vertikal maupun horizontal. sedangkan $g(2)=0$ karena kita tidak bisa mengisi $2\times2$ dengan ubin berbentuk **L**

---
## relasi akhir
* $f(x)=f(x-1)+f(x-2)+2\times g(x)$
* $g(x)=g(x-1)+f(x-3)$
* $f(0)=1$
* $f(1)=1$
* $f(2)=2$
* $g(0)=1$
* $g(1)=0$
* $g(2)=0$

### tabel $f(x)$ dan $g(x)$

| $x$ | $f(x)$ | $g(x)$ |
| -------- | -------- | -------- |
| $0$ | $1$ | $1$|
| $1$ | $1$ | $0$|
| $2$ | $2$ | $0$|
| $3$ | $5$ | $1$|
| $4$ | $11$ | $2$|
| $5$ | $24$ | $4$|
| $6$ | $53$ | $9$|
| $7$ | $117$ | $20$|
| $8$ | $258$ | $44$|
| $9$ | $569$ | $97$|
| $10$ | $1255$ | $214$|

jawaban akhir ada di $f(10)=1255$