I wrote a program to solve Project Euler Problem #215 (see below for description) using memoization, and when I got access to the PE forums, I saw everyone else wrote programs that also used dynamic programming/memoization techniques.
However, from this stackoverflow answer, Dietrich Epp solved it in Haskell using a sparse matrix of NxN dimensions (an adjacency matrix) and then multiplied the matrix by a 1xN vector to arrive at the solution.
Quote from the poster Dietrich Epp:
You compute each possible way to tile a row. Let's say there are N ways to tile a row. Make an NxN matrix. Element i,j is 1 if row i can appear next to row j, 0 otherwise. Start with a vector containing N 1s. Multiply the matrix by the vector a number of times equal to the height of the wall minus 1, then sum the resulting vector.
How come the matrix x vector solution is viable for this problem, as in what property is it exploiting to solve the question?
Thanks in advance!
Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal and vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".
For example, the following 9x3 wall is not acceptable due to the running crack shown in red:
There are eight ways of forming a crack-free 93 wall, written W(9,3) = 8.