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 sizen+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
anddp[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 formuladp[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 resultdp[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
.
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