900 - Brick Wall Patterns
Given wall bricks of size 2x1 units, what is the number of all possible brick patterns for a wall of height 2 units and a length of units?
Let fn be the number of ways to assembly a wall of length n.
There are two ways of assembling a wall of length n, and a height of 2 units. We either place a vertical bar at its beginning and assemble a wall of length n - 1 or we place two horizontal bars on top of one another and assemble then a wall of length n - 2. That is,
- fn: = fn - 1 + fn - 2.
The base cases are already given in the example, which leads us to:
You can solve the series blazingly fast in O(n) using a bottom-up dynamic programming solution.
Use a 64-bit field to hold the results; f50 > 232 - 1.
1 2 3 4 5 6 7 50 0
1 2 3 5 8 13 21 20365011074