# Project Euler – Lattice Path (Part 5)

Apart from the recursive solutions an iterative approach for solving the lattice path problem exists as well.

Again full credit goes to Pim Spelier. I really need to find this guy online. So I can properly link to him.

All my work is to translate the given algorithm to Java and dissect it in a way, so that I can understand the solution. The algorithm performs nicely within a blink of a second. Even if I increase the grid size above 20.

So how does it work?

First we create a two-dimensional array. Let’s use the 2×2 grid as an example.
As of long[][] grid = new long[gridHeight + 1][gridWidth + 1] our empty two-dimensional array looks like this: Actually all grid cells hold an initial value of 0.

Next step is to fill the grid partially:

for (int i = 0; i <= gridHeight; i++) {
grid[i] = 1;
}

for (int j = 0; j <= gridWidth; j++) {
grid[j] = 1;
} And then we fill in the remaining slots:

for (int i = 1; i <= gridHeight; i++) {
for (int j = 1; j <= gridWidth; j++) {
grid[i][j] = grid[i – 1][j] + grid[i][j – 1];
}
} After the first iteration (i = 1 and j = 1) the grid looks like this: After the second iteration (i = 1 and j = 2): Third iteration (i = 2 and j = 1): And finally (i = 2 and j = 2), which is exactly Pascal’s triangle: There is one more blog post to write about this problem. It will be about a combinatorial solution.