UVa 900

From Algorithmist
Jump to: navigation, search

900 - Brick Wall Patterns[edit]

UVa link

Summary[edit]

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 n\leq 50 units?

Explanation[edit]

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:

f_{n}:={\begin{cases}1,&n=1\\2,&n=2\\f_{{n-1}}+f_{{n-2}},&n>2\\\end{cases}}

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.

Gotchas[edit]

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

Input[edit]

1
2
3
4
5
6
7
50
0

Output[edit]

1
2
3
5
8
13
21
20365011074

Solution[edit]

Solution link