UVa 900
900 - Brick Wall Patterns[edit]
Summary[edit]
Given wall bricks of size units, what is the number of all possible brick patterns for a wall of height units and a length of units?
Explanation[edit]
Let be the number of ways to assembly a wall of length .
There are two ways of assembling a wall of length , and a height of 2 units. We either place a vertical bar at its beginning and assemble a wall of length or we place two horizontal bars on top of one another and assemble then a wall of length . That is,
- .
The base cases are already given in the example, which leads us to:
Which is the fibonacci series, with a slightly different base! (This proof was originally written by Schultz, on 21:20, 26 May 2007 (EDT))
You can solve the series blazingly fast in using a bottom-up dynamic programming solution.
Gotchas[edit]
Use a 64-bit field to hold the results; .
Input[edit]
1 2 3 4 5 6 7 50 0
Output[edit]
1 2 3 5 8 13 21 20365011074