By: Nicholas Duchon

I have attached two Flash presentations that I hope help you visualize the recursion in this problem, and help you develop the matrix solution.

The Algorithm (fixed):

int paths (r, c, n)

if (r == n)
return 1 // top row

if (c == n)
return 1 // right column

return paths
(r+1, c, n) + paths (r, c+1, n)

In words:

- the number of paths from this cell is:
- 1 if on the top row
- 1 if on the right-most (last) column
- sum of number of paths from cell above PLUS

number of paths from cell to right

Links to presentation in Flash:

ND.