Suppose you are given a rectangular grid of size 4 x n. You are also given...

 

Transcribed Image Text:

Suppose you are given a rectangular grid of size 4 x n. You are also given an endless bag of dominoes, each of size 2 by 1. Write a dynamic programming algorithm to find the total number of unique ways the 4 x n board can be exactly tiled (no "overflow", no "overlap"). State (with justification) the running time of your algorithm. For example, if the input given is n = 2, then the solution is 5, Figure 1 shows all of the combinations of fully tiled boards of width n = 2: Figure 1: All 5 ways of tiling a 4 x 2 board with dominoes Suppose you are given a rectangular grid of size 4 x n. You are also given an endless bag of dominoes, each of size 2 by 1. Write a dynamic programming algorithm to find the total number of unique ways the 4 x n board can be exactly tiled (no "overflow", no "overlap"). State (with justification) the running time of your algorithm. For example, if the input given is n = 2, then the solution is 5, Figure 1 shows all of the combinations of fully tiled boards of width n = 2: Figure 1: All 5 ways of tiling a 4 x 2 board with dominoes