Posted on by Kalkicode
Code Dynamic Programming

# 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`.

## 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.

Categories
Relative Post