Skip to main content

Tiling problem using dynamic programming

In this article, we will explore the tiling problem and its solution using dynamic programming. The tiling problem involves finding the number of ways to tile a given space using 2x1 tiles. We will present an algorithm based on dynamic programming to solve this problem efficiently.

Problem Statement

Given a space of length n, we want to find the number of ways to tile it using 2x1 tiles. The tiles can be placed either horizontally or vertically to cover the entire space without any overlaps or gaps.

Pseudocode Algorithm with Explanation

We can solve the tiling problem using dynamic programming. The idea is to build the solution iteratively based on previously computed subproblems. Here's the pseudocode algorithm for solving the tiling problem: 


function findResult(n):
	if n <= 0:
		return
	dp = array of size (n+1)
	dp[0] = 0
	dp[1] = 1

	for i = 2 to n:
		dp[i] = dp[i-1] + dp[i-2]

	print("Given: " + n)
	print("Result: " + dp[n])

Let's break down the algorithm:

  • We start by checking if the given input n is less than or equal to zero. If so, there are no ways to tile the space, and we return.
  • We initialize an array dp of size n+1 to store the results of subproblems. The index of the array represents the length of the space, and the value represents the number of ways to tile that space.
  • We set the initial values dp[0] = 0 and dp[1] = 1 since there is only one way to tile a space of length 1 (using a single 2x1 tile).
  • We iterate from 2 to n and compute the number of ways to tile each length using the formula dp[i] = dp[i-1] + dp[i-2]. This recurrence relation holds because we can either place a vertical tile at the end or two horizontal tiles to cover the remaining length.
  • Finally, we print the given value n and the calculated result dp[n].

Code solution

// C Program
// Tiling problem dynamic programming
#include <stdio.h>

void findResult(int n)
{
    if(n <= 0)
    {
        return ;
    }
    int dp[n+1];
    // Set initial values
    dp[0] = 0; 
    dp[1] = 1;

    // Calualte result
    for(int i=2; i<= n;++i)
    {
        dp[i]  = dp[i-1] + dp[i-2];
    }
    // Display given value
    printf("\n Given  : %d", n);
    // Display calculated result
    printf("\n Result : %d",dp[n]);
}
int main()
{
    
    // Test case
    findResult(7);
    findResult(3);
    return 0;
}

Output

 Given  : 7
 Result : 13
 Given  : 3
 Result : 2
// Java program for
// Tiling problem dynamic programming
public class TilingProblem
{
	public void findResult(int n)
	{
		if (n <= 0)
		{
			return;
		}
		int[] dp = new int[n + 1];
		// Set initial values
		dp[0] = 0;
		dp[1] = 1;
		// Calualte result
		for (int i = 2; i <= n; ++i)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		// Display given value
		System.out.print("\n Given : " + n);
		// Display calculated result
		System.out.print("\n Result : " + dp[n]);
	}
	public static void main(String[] args)
	{
		TilingProblem task = new TilingProblem();
		// Test
		task.findResult(7);
		task.findResult(3);
	}
}

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
// Include header file
#include <iostream>
using namespace std;

// C++ program for
// Tiling problem dynamic programming

class TilingProblem
{
	public: void findResult(int n)
	{
		if (n <= 0)
		{
			return;
		}
		int dp[n + 1];
		// Set initial values
		dp[0] = 0;
		dp[1] = 1;
		// Calualte result
		for (int i = 2; i <= n; ++i)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		// Display given value
		cout << "\n Given : " << n;
		// Display calculated result
		cout << "\n Result : " << dp[n];
	}
};
int main()
{
	TilingProblem *task = new TilingProblem();
	// Test
	task->findResult(7);
	task->findResult(3);
	return 0;
}

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
// Include namespace system
using System;
// Csharp program for
// Tiling problem dynamic programming
public class TilingProblem
{
	public void findResult(int n)
	{
		if (n <= 0)
		{
			return;
		}
		int[] dp = new int[n + 1];
		// Set initial values
		dp[0] = 0;
		dp[1] = 1;
		// Calualte result
		for (int i = 2; i <= n; ++i)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		// Display given value
		Console.Write("\n Given : " + n);
		// Display calculated result
		Console.Write("\n Result : " + dp[n]);
	}
	public static void Main(String[] args)
	{
		TilingProblem task = new TilingProblem();
		// Test
		task.findResult(7);
		task.findResult(3);
	}
}

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
package main
import "fmt"
// Go program for
// Tiling problem dynamic programming

func findResult(n int) {
	if n <= 0 {
		return
	}
	var dp = make([] int, n + 1)
	// Set initial values
	dp[0] = 0
	dp[1] = 1
	// Calualte result
	for i := 2 ; i <= n ; i++ {
		dp[i] = dp[i - 1] + dp[i - 2]
	}
	// Display given value
	fmt.Print("\n Given : ", n)
	// Display calculated result
	fmt.Print("\n Result : ", dp[n])
}
func main() {
	// Test
	findResult(7)
	findResult(3)
}

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
<?php
// Php program for
// Tiling problem dynamic programming
class TilingProblem
{
	public	function findResult($n)
	{
		if ($n <= 0)
		{
			return;
		}
		$dp = array_fill(0, $n + 1, 0);
		// Set initial values
		$dp[0] = 0;
		$dp[1] = 1;
		// Calualte result
		for ($i = 2; $i <= $n; ++$i)
		{
			$dp[$i] = $dp[$i - 1] + $dp[$i - 2];
		}
		// Display given value
		echo("\n Given : ".$n);
		// Display calculated result
		echo("\n Result : ".$dp[$n]);
	}
}

function main()
{
	$task = new TilingProblem();
	// Test
	$task->findResult(7);
	$task->findResult(3);
}
main();

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
// Node JS program for
// Tiling problem dynamic programming
class TilingProblem
{
	findResult(n)
	{
		if (n <= 0)
		{
			return;
		}
		var dp = Array(n + 1).fill(0);
		// Set initial values
		dp[0] = 0;
		dp[1] = 1;
		// Calualte result
		for (var i = 2; i <= n; ++i)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		// Display given value
		process.stdout.write("\n Given : " + n);
		// Display calculated result
		process.stdout.write("\n Result : " + dp[n]);
	}
}

function main()
{
	var task = new TilingProblem();
	// Test
	task.findResult(7);
	task.findResult(3);
}
main();

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
#  Python 3 program for
#  Tiling problem dynamic programming
class TilingProblem :
	def findResult(self, n) :
		if (n <= 0) :
			return
		
		dp = [0] * (n + 1)
		#  Set initial values
		dp[0] = 0
		dp[1] = 1
		i = 2
		#  Calualte result
		while (i <= n) :
			dp[i] = dp[i - 1] + dp[i - 2]
			i += 1
		
		#  Display given value
		print("\n Given : ", n, end = "")
		#  Display calculated result
		print("\n Result : ", dp[n], end = "")
	

def main() :
	task = TilingProblem()
	#  Test
	task.findResult(7)
	task.findResult(3)

if __name__ == "__main__": main()

Output

 Given :  7
 Result :  13
 Given :  3
 Result :  2
#  Ruby program for
#  Tiling problem dynamic programming
class TilingProblem 
	def findResult(n) 
		if (n <= 0) 
			return
		end

		dp = Array.new(n + 1) {0}
		#  Set initial values
		dp[0] = 0
		dp[1] = 1
		i = 2
		#  Calualte result
		while (i <= n) 
			dp[i] = dp[i - 1] + dp[i - 2]
			i += 1
		end

		#  Display given value
		print("\n Given : ", n)
		#  Display calculated result
		print("\n Result : ", dp[n])
	end

end

def main() 
	task = TilingProblem.new()
	#  Test
	task.findResult(7)
	task.findResult(3)
end

main()

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
// Scala program for
// Tiling problem dynamic programming
class TilingProblem()
{
	def findResult(n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		var dp: Array[Int] = Array.fill[Int](n + 1)(0);
		// Set initial values
		dp(0) = 0;
		dp(1) = 1;
		var i: Int = 2;
		// Calualte result
		while (i <= n)
		{
			dp(i) = dp(i - 1) + dp(i - 2);
			i += 1;
		}
		// Display given value
		print("\n Given : " + n);
		// Display calculated result
		print("\n Result : " + dp(n));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: TilingProblem = new TilingProblem();
		// Test
		task.findResult(7);
		task.findResult(3);
	}
}

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2
// Swift 4 program for
// Tiling problem dynamic programming
class TilingProblem
{
	func findResult(_ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		var dp: [Int] = Array(repeating: 0, count: n + 1);
		// Set initial values
		dp[0] = 0;
		dp[1] = 1;
		var i: Int = 2;
		// Calualte result
		while (i <= n)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
			i += 1;
		}
		// Display given value
		print("\n Given : ", n, terminator: "");
		// Display calculated result
		print("\n Result : ", dp[n], terminator: "");
	}
}
func main()
{
	let task: TilingProblem = TilingProblem();
	// Test
	task.findResult(7);
	task.findResult(3);
}
main();

Output

 Given :  7
 Result :  13
 Given :  3
 Result :  2
// Kotlin program for
// Tiling problem dynamic programming
class TilingProblem
{
	fun findResult(n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		val dp: Array < Int > = Array(n + 1)
		{
			0
		};
		// Set initial values
		dp[0] = 0;
		dp[1] = 1;
		var i: Int = 2;
		// Calualte result
		while (i <= n)
		{
			dp[i] = dp[i - 1] + dp[i - 2];
			i += 1;
		}
		// Display given value
		print("\n Given : " + n);
		// Display calculated result
		print("\n Result : " + dp[n]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: TilingProblem = TilingProblem();
	// Test
	task.findResult(7);
	task.findResult(3);
}

Output

 Given : 7
 Result : 13
 Given : 3
 Result : 2

Resultant Output Explanation

Let's analyze the output of the provided code for the test cases n = 7 and n = 3: 


Given: 7
Result: 13

Given: 3
Result: 2

For the first test case n = 7, the output Result: 13 indicates that there are 13 different ways to tile a space of length 7 using 2x1 tiles.

For the second test case n = 3, the output Result: 2 indicates that there are 2 different ways to tile a space of length 3 using 2x1 tiles.

Time Complexity of the Code

The time complexity of the provided code is O(n) since we iterate from 2 to n once to calculate the number of ways to tile each length. This linear time complexity makes the algorithm efficient for larger values of n.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment