# project euler – Problem 15

November 8, 2011
By

(This article was first published on YGC » R, and kindly contributed to R-bloggers)

```Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20x20 grid?
```

Using recursive algorithm can solved this problem well. For optimized the running time, I use a matrix to cache previously called functions, as I did in Problem 164.

?View Code RSPLUS
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ``` ```find.routes.internal <- function(x,y) { cnt <- cacheMat[x+1,y+1] if (cnt != 0) return(cnt)   if (y >0) cnt <- cnt+find.routes.internal(x,y-1) if (x >0) cnt <- cnt+find.routes.internal(x-1,y) if (x ==0 && y ==0) cnt <- cnt+1   cacheMat[x+1,y+1] <<- cnt   return(cnt) }   find.routes <- function(x,y) { cacheMat <- matrix(0, nrow=x+1, ncol=y+1) cnt <- find.routes.internal(x,y) return(cnt) }```

#### Related Posts

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...