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.

Without further ado…

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][0] = 1;
}

for (int j = 0; j <= gridWidth; j++) {
    grid[0][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.