- 512,586 hits
Make the frequent cases fast and the rare case correct
Problem 15 – Project Euler – Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
February 21, 2011Posted by on
Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner? – Project Euler
How many routes are there through a 20×20 grid?
For a 2×2 grid there are 6 possible paths so use the factorial formula for binomial coefficient.
consider moving east as E and south as S.
the 6 combinations are EESS, ESES, ESSE, SEES, SESE, SSEE.
for 2×1 grid.
3 combinations. ESE, EES, SEE – 3 paths – 3C1
This is a combination problem.
For a mxn grid the possible paths is given by
An article about Binomial Coefficents – Pascals triangle and Binomial coefficient.