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.
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) } |
- Pingback on 2011/11/09/ 15:47
Scala, 3行代码，5秒搞定：
scala> def lenOfPa...
This is a basic problem of combinatorics. The number of routes through a X by Y rectangle is given by C(X+Y,X), where C represents combinations. (http://en.wikipedia.org/wiki/Binomial_coefficient). In R:
choose(20+20,20)
When an elegant closed form solution to a problem is presented, use it!
Reply