Tile a 2 x n Floor with Dominoes
Problem
A floor is 2 rows high and n columns wide. You have many dominoes of size 2 x 1 that can be placed standing (1 column) or lying (2 columns, two of them stacked). Count the number of ways to cover the floor completely. Print the count.
Constraints
- 1 <= n <= 60
Examples
Input
3
Output
3
Input
4
Output
5
Solutions
Look at the first column only. A standing domino leaves a floor of width n - 1. Two lying dominoes leave width n - 2. So ways(n) = ways(n - 1) + ways(n - 2): the Fibonacci numbers. The memo makes the recursion O(n).
/*
* Problem : Count the tilings.
* Input : n.
* Output : The count.
* Approach: Recursion with memo
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 2: The first column is covered by one standing domino (n - 1 columns remain), or two lying dominoes cover two columns (n - 2 remain).
static long ways(int n, long[] memo) {
if (n <= 1) {
return 1;
}
// Step 3: The memo stops the same n from being solved again and again.
if (memo[n] != 0) {
return memo[n];
}
memo[n] = ways(n - 1, memo) + ways(n - 2, memo);
return memo[n];
}
// This method solves the task. It receives the input and returns the answer.
static long solve(long n) {
// Step 1: memo[n] keeps the answer for width n. 0 means not known yet.
return ways((int) n, new long[(int) n + 2]);
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(solve(n));
}
}
Hints (2)
- What covers the first column?
- Which known sequence is this?