Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Dynamic programming approach in action

Theory

Board tiling

Report a typo

Imagine that there is a board of N (1 ≤ N ≤ 40) length and an unlimited inventory of tiles of length 1, 2, and 3. Write a program that reads the length of the board from the console and prints the number of possible ways you can tile that board with those tiles.

The picture below shows an example of such tiling:

example tiling

As you can see, there are 7 different ways you can tile a board of length 4 with tiles of length 1, 2 and 3.

Sample Input 1: 

4

Sample Output 1: 

7

Sample Input 2: 

26

Sample Output 2: 

4700770

Sample Input 3: 

36

Sample Output 3: 

2082876103
Write a program in Java 17
import java.util.Scanner;

class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int boardSize = scanner.nextInt();

// Write your code here

}
}
___

Create a free account to access the full topic