Dynamic Programming

Some tiling problems

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

We place a tile horizontally. Then, to complete the tiling, we are forced to place another tile horizontally below (or above) it. This leaves an (n-2)×2 grid, that can be tiled in T(n-2) ways.

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

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

For the base case we have

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)

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

T(2) = 2 (place two tiles horizontally, or two tiles vertically)

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

T(3) = T(2) + T(1) = 2 + 1 = 3
T(4) = T(3) + T(2) = 3 + 2 = 5
…

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⁸? The solution we just wrote requires us to store 10⁸ 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);
           }
         }

A more complicated tiling problem

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

A 2×1 tile as before

       	    -- -- 
       	   |  |  |
       	    -- --

An L-shaped tile covering 3 squares

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.

Indian Computing Olympiad

Dynamic Programming

Some tiling problems

A more complicated tiling problem

Basic topics

Advanced topics