### Description

In how many ways can you tile a 3xn rectangle with 2×1 dominoes?

Here is a sample tiling of a 3×12 rectangle.

### Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.

### Output

For each test case, output one integer number giving the number of possible tilings.

### Sample Input

2 8 12 -1

### Sample Output

3 153 2131

Solution below . . .

### Steps for Solving Dynamic Programming Problems

**1. Define subproblems**

Let be the number of tilings of a 3xN rectangle (which is what we’re looking for) and let denote the number of tilings of a 3xN rectangle with one of its corner squares removed.

******** ******** ******** f(n) ******** ******** ******* g(n)

**2. Write down the recurrence that relates subproblems**

The recurrence functions are and . The functions can be illustrated as follows:

******** AA******* AA****** A******* ******** = BB******* + B******* + A******* ******** CC******* B******* BB****** f(n) = f(n-2) + g(n-1) + g(n-1) ******** A******** AA******* ******** = A******** + BB******* ******* ******** CC****** g(n) = f(n-1) + g(n-2)

If you’re wondering why patterns like

AA******* BC******* BC*******

or

AB******* AB******* CC******

are not represented, notice that they are subsets of existing patterns and thus already accounted for.

**3. Recognize and solve the base cases**

The base cases are: . (Re , there’s no way to remove the corner from a 3×0 rectangle.)

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n != -1) { // Optimization: If n is odd, the number of tilings = 0. if (n % 2 == 1) { System.out.println(0); } else { System.out.println(f(n)); } n = sc.nextInt(); } sc.close(); } private static int f(int n) { if (n == 0) return 1; if (n == 1) return 0; return f(n-2) + 2 * g(n-1); } private static int g(int n) { if (n < 2) return n; return f(n-1) + g(n-2); } }