234. Tiling With Dominoes
Core1000 ms256 MBSolved by 0%
A board is 2 squares tall and n squares wide. Print how many ways it can be
covered completely by 2x1 dominoes, which may be laid flat or upright.
Think about the rightmost column. Either one upright domino fills it, leaving a
board of width n - 1, or two flat dominoes fill the last two columns,
leaving a board of width n - 2. Those two cases do not overlap and cover
everything.
That gives a familiar recurrence, and a familiar performance problem if you write it without remembering anything.
Constraints - `1 ≤ n ≤ 86` - The answer fits in a signed 64-bit integer.
Input
A single line containing one integer n, the width of the board.
Output
Print one integer, the number of complete tilings.
Input4
Output5
Noteis small enough to draw all five tilings
Input1
Output1
Noteis a single column, filled one way by an upright domino
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.