Given a “2 x n” board and tiles of size “2 x 1”, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
Input n = 3 Output: 3 Explanation: We need 3 tiles to tile the board of size 2 x 3. We can tile the board using following ways 1) Place all 3 tiles vertically. 2) Place first tile vertically and remaining 2 tiles horizontally. 3) Place first 2 tiles horizontally and remaining tiles vertically Input n = 4 Output: 5 Explanation: For a 2 x 4 board, there are 5 ways 1) All 4 vertical 2) All 4 horizontal 3) First 2 vertical, remaining 2 horizontal 4) First 2 horizontal, remaining 2 vertical 5) Corner 2 vertical, middle 2 horizontal
Let “count(n)” be the count of ways to place tiles on a “2 x n” grid, we have following two ways to place first tile.
1) If we place first tile vertically, the problem reduces to “count(n-1)”
2) If we place first tile horizontally, we have to place second tile also horizontally. So the problem reduces to “count(n-2)”
Therefore, count(n) can be written as below.
count(n) = n if n = 1 or n = 2 count(n) = count(n-1) + count(n-2)
The above recurrence is noting but Fibonacci Number expression. We can find n’th Fibonacci number in O(Log n) time, see below for all method to find n’th Fibonacci Number.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements