ISourceCode

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?

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: