8
[Golang] Lattice paths - Problem 15 - Project Euler
source link: http://siongui.github.io/2017/12/25/go-lattice-paths-problem-15-project-euler/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Golang] Lattice paths - Problem 15 - Project Euler
December 25, 2017
Problem: [1]
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Solution:
Observe the case of a 2x2 grid. We can found that to move from top left to bottom right, we need to move 2 down steps and 2 right steps. The total number of routes in 2x2 grid is hence equivalent to total number of combinations of 2 down steps and 2 right steps in a row, i.e., (42) = (4!)/(2!2!) = 6.
So, the routes in 20x20 grid = (2010) = (20!)/(10!10!) = 184756
References:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK