# UVa 900

## Contents |

## [edit] 900 - Brick Wall Patterns

## [edit] Summary

Given wall bricks of size 2*x*1 units, what is the number of all possible brick patterns for a wall of height 2 units and a length of units?

## [edit] Explanation

Let *f*_{n} 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,

*f*_{n}: =*f*_{n - 1}+*f*_{n - 2}.

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 *O*(*n*) using a bottom-up dynamic programming solution.

## [edit] Gotchas

Use a 64-bit field to hold the results; *f*_{50} > 2^{32} - 1.

## [edit] Input

1 2 3 4 5 6 7 50 0

## [edit] Output

1 2 3 5 8 13 21 20365011074