Let us first define states to solve this dynamic programming problem. The first state, f(n) = number of ways to tile n \times 2 grid. The next state, g(n) = number of ways to tile n \times 2 grid **plus the top square in the (n+1)th column**, and h(n) = number of ways to tile n \times 2 grid **plus the bottom square in the (n+1)th column**. Note that the definitions are *symmetric*, so it's okay if you only defined one of them, since g(n) = h(n).

The recursion involves f(n) as a function of f and g, as well as g(n) as a function of f and g.

The recursion for g(n) is g(n) = g(n-1) + f(n-1). The two cases correspond to the square in (n+1)th column being covered by a horizontal 2 x 1, or a L-shaped tile.

The recursion for f(n) is f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2). The four cases correspond to the right-top corner square being covered with vertical 2 x 1 tile, horizontal 2 x 1 tile, L shaped tile and L-shaped tile the other way. This simplifies to f(n) = f(n-1) + f(n-2) + 2*g(n-2).

A crucial step is to figure out the base cases. We can define it for n = 0, 1 or n = 1, 2.

g[0] is 0 as we cannot tile a single square.

g[1] is 1 as we can put an L-shaped tile.

g[2] is 2 as we can first put a vertical 2 x 1 tile followed by an L-shaped tile. The second is to put an L-shaped tile first followed by a horizontal 2 x 1 tile.

The following is the solution to the Tiling Problem v2.0 in cpp:

type=codeblock|id=dptilev2cpp|autocreate=cpp|show_output=1#include <bits/stdc++.h>using namespace std;#define MOD 1000003long int f[100001],g[100001];int main(){g[1] = 1;g[2] = 2;f[1] = 1;f[2] = 2;for(int i = 3; i < 100000; i++){g[i] = (f[i - 1] + g[i - 1]) % MOD;f[i] = (f[i - 1] +f[i - 2] + 2 * g[i - 2]) % MOD;}int queries[10] = {3, 10, 23, 60, 269, 832, 1597, 5189, 25987, 76401};int q = 10;for (int i = 0; i < q; i++){cout << "Number of ways of tiling " << queries[i] << "x2 tiles: " << f[ queries[i] ] << endl;}return 0;}

The following is the solution to the Tiling Problem v2.0 in py:

type=codeblock|id=dptilev2py|autocreate=python3|show_output=1def tile(n):ff = [None]*(n+1)gg = [None]*(n+1)ff[0] = 1 # if we have no grid, there is only one way to tile it!ff[1] = 1 # we must place a single tile vertically# ff[2] = 2 # place two tiles horizontally, or two tiles vertically (if you are not happy with n = 0)gg[0] = 0 # cannot tile a single squaregg[1] = 1 # use exactly one L-shaped tile# recurse. do all operations % 1000003for ii in range(2, n+1):ff[ii] = (ff[ii-2] + ff[ii-1] + 2*gg[ii-2]) % 1000003gg[ii] = (ff[ii-1] + gg[ii-1]) % 1000003return ff[n]queries = [3, 10, 23, 60, 269, 832, 1597, 5189, 25987, 76401]for itest in range(0,len(queries)):n = int(queries[itest])answer = tile(n)print(str(queries[itest])+"x2: " + str(answer))