Tiling_with_Dominoes.cpp

/*
https://www.geeksforgeeks.org/tiling-with-dominoes/

Domino Tiling Problem
C++ program to find no. of ways to fill a 3xn board with 2x1 dominoes.
Given a positive integer n, find the number of ways to fill an n×3 board by 2×1 dominos.
Input: A positive integer n. 
Output: The number of ways to fill an n×3 board by 2×1 dominos.
*/
#include <iostream>
using namespace std;

int countWays(int n)
{
	int A[n + 1], B[n + 1];
	A[0] = 1, A[1] = 0, B[0] = 0, B[1] = 1;
	for (int i = 2; i <= n; i++) {
		A[i] = A[i - 2] + 2 * B[i - 1];
		B[i] = A[i - 1] + B[i - 2];
	}

	return A[n];
}

int main()
{
	int n = 8;
	cout << countWays(n);
	return 0;
}