We have an n×2 grid to be tiled.

<-------- n ---------> -- -- -- -- -- -- -- | | | | | |..| | -- -- -- -- -- -- | | | | | |..| | -- -- -- -- -- -- --

We have with us a supply of rectangular tiles of size 2×1. Each tile can be rotated and laid horizontally or vertically.

-- -- | | | -- --

How many ways can we tile the n×2 grid using these tiles?

**Solution**

Let T(n) denote the number of ways of tiling an n×2 grid.

We begin the tiling at the left end. We have two possibilities:

- We place a tile vertically. This leaves an (n-1)×2 grid, that can be tiled in T(n-1) ways
- T(0) = 1 (if we have no grid, there is only one way to tile it!)
- T(1) = 1 (we must place a single tile vertically)
- T(2) = 2 (place two tiles horizontally, or two tiles vertically)
- T(3) = T(2) + T(1) = 2 + 1 = 3
- T(4) = T(3) + T(2) = 3 + 2 = 5
- …
- A 2×1 tile as before
- An L-shaped tile covering 3 squares

Thus, we can express T(n) using the recurrence:

T(n) = T(n-1) + T(n-2)

For the base case we have

If you are not happy with T(0) as a base case, you can add

Then, we can compute T(k) for any k starting at the base case

This yields the familiar Fibonacci sequence: T(n) is the nth Fibonacci number.

As we have seen, computing T(n) recursively involves wasteful recomputation of subproblems. For instance, T(8) generates subproblems as follows:

T(8) / \ T(7) T(6) / \ / \ T(6) T(5) T(5) T(4) / \ / \ / \ / \ T(5) T(4) T(4) T(3 T(4) T(3) T(3 T(2) . . . . . . . . . . . . . . . .

Observe that T(6) is computed twice, T(5) is computed 3 times, T(4) is computed 5 times, …

We can modify the recursive procedure to store values that are already computed and avoid recomputation.

Initialize S[1..N] to -1 // -1 denotes that S[i] is yet to // be computed T(i) { if (S[i] != -1){ // S[i] has been computed return(S[i]) }else{ // Compute T[i] and store in S[i] if (i == 1){ S[i] = 1; return(1); } if (i == 2){ S[i] = 1; return(1); } if (i > 2){ S[i] = T(i-1) + T(i-2); return(S[i]); } } }

This will compute T(n) in time proportional to n, but there are other overheads associated with recursive calls. There is also a limit to the depth of recursion --- how large an n you can use for nested recursive calls.

A more efficient solution is to start with T(1) and T(2) and work upwards to n.

T(i) { if (i <= 2){ return(1); } if (i > 2){ S[1] = 1; S[2] = 1; for (j = 2; j <= i; j++){ S[j] = S[j-1] + S[j-2]; } return(S[j]); } }

What if we want T(n) for very large n, for instance n =
10^{8}? The solution we just wrote requires us
to store 10^{8} values in the array S. Note,
however, that we only need the previous two values in
the array, so we can make do by keeping two values at a
time.

T(i) { if (i <= 2){ return(1); } if (i > 2){ secondlast = 1; // T(i-2) last = 1; // T(i-1) for (j = 2; j <= i; j++){ new = last + secondlast; // T(i) = T(i-1) --> T(i-2) secondlast = last; // T(i-1) --> T(i-2) last = new; // T(i) --> T(i-1) } return(last); } }

Again we want to tile an n×2 grid, but we have two types of tiles:

-- -- | | | -- --

-- -- | | | -- -- | | --

How many ways can we tile the n×2 grid using these tiles?

**Solution**

As before, let us see how we can begin our tilings from the left end. There are now four possibilities for the leftmost tile(s):

<----- n-1 -----> <---- n-2 -----> -- ---------- ... -- ------------- ... -- | | | | | | | |---------- ... -- ------------- ... -- | | | | | | -- ---------- ... -- ------------- ... -- <---- n-2 -----> <----- n-1 ------> -- ---------- ... -- -- ---------- ... -- | | | | | | | -- ------- ... -- | -- ------- ... -- | | | | | | -- ---------- ... -- -- ---------- ... -- <----- n-1- -----> <---- n-2----->

If we use an L-shaped tile initially, we are left with a shape in which either the top or bottom row has one extra square.

Let

- f(n) = number of ways of tiling an n×2 rectangle.
- g(n) = number of ways of tiling an n×2 rectangle with an extra square in the bottom row.
- h(n) = number of ways of tiling an n×2 rectangle with an extra square in the top row.

From the cases above, we can see that

f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2)

Observe that, by symmetry, h(n) = g(n), so we can simplify this to

f(n) = f(n-1) + f(n-2) + 2g(n-2)

In a similar fashion, we can write a recurrence for g(n) by looking at what we can do initially.

<------ n -----> <------ n -----> ------- ... -- ------- ... -- | | | | | -- |---- ... -- ----- ---- ... -- | | | | | | ---------- ... -- ---------- ... -- <--- n-1 --> <-- n-1 --->

g(n) = f(n-1) + h(n-1) = f(n-1) + g(n-1), since g(n) = h(n)

We can write down base cases, as before:

- f(0) = 1, f(1) = 1
- g(0) = 0 (cannot tile a single square),

g(1) = 1 (use exactly one L-shaped tile)

As before, we could explicitly add a base case f(2) = 2, in which case we don't need the case g(0) = 0.

To calculate this, we start with the base case and work upwards to f(k) or g(k) for any k, as in the previous example.

Again, we should *not* use naive recursion,
because this will involve wasteful recomputation of
smaller values.

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky