Challenge: Domino Tiles

Lab Java Beginner 10 points

How many ways can you cover a 2 × n board with 1 × 2 dominoes (each placed upright or lying down)? Fill a DP table bottom-up.

Input

One whole number n (1 ≤ n ≤ 85).

Output

The number of ways.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

Look at the right end of the board: either one upright domino (leaving 2 × (n−1)) or two lying flat (leaving 2 × (n−2)).

So dp[i] = dp[i - 1] + dp[i - 2], with dp[0] = dp[1] = 1. Use long.

Solution explanation

It's Fibonacci in disguise! O(n) time. The answer for n = 85 is about 4 × 10¹⁷ – recursion without a table would never finish.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] dp = new long[n + 2];
        dp[0] = 1;   // an empty board: one way (place nothing)
        dp[1] = 1;   // one upright domino
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];   // end with one upright, or two lying down
        }
        System.out.println(dp[n]);
    }
}

Output

Answer