题目
Starting in the top left corner of a 2x2 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 20x20 grid?
解答: 这道题最简单的解法当然是下面这种： 为什么是这样？因为你走了40步，往右边走20步，往下面走20步。不管是怎么样的走法，都是这样子。如果你把走法记录下来，那就是一个长度为40的序列。而走的顺序你是不可能跳跃的，你往右只能是一步步往右，往下也是这样子，这是最重要的限制条件，所以这里没有排列要考虑。 如果我确定了这40个位置里往右要占的位置，那剩下的就是往下的，而往下的只有一种情况了，那就是从1到20，去填剩下的位置。所以这长为40的序列，我只要看往右或往下一种就可以了，因为我填了一种，另一种是确定的。 而往右你确定了要占的位置，那也是从1到20顺序填下去，也是只有一种情况。所以这道题就变成了，从40个位置里，拿出来20个位置，有多少种情况，于是就是上面这个最简单的解了。 但是这里练编程嘛，数学我不懂，我也能够用数值计算的方法来解出来，要的就是这样子。这道题可以用递归。我从终点开始，走回起点，按照往上、往左的方向走。
find.routes.internal <- memoise::memoise(function(x,y, cacheMat) {
cnt <- cacheMat[x+1,y+1]
if (cnt != 0)
return(cnt)
if (y >0)
cnt <- cnt + find.routes.internal(x,y-1, cacheMat)
if (x >0)
cnt <- cnt + find.routes.internal(x-1,y, cacheMat)
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, cacheMat)
return(cnt) } 递归虽然爽，但是这里面重复计算的太多，时间复杂指数是，整个计算会很慢，解决方法就是缓存结果。用memoise包是最简单的，配合递归，是相当好用。那么计算也是瞬间的事情。一回车答案就出来了。 生信学生的解法 当然这个问题，对于我们生信的学生来说，简单得不要太简单，想想我们上课是不是写过用动态规划来实现两序列的比对？所以这道题要是不能如此这般地解，可能要怀疑自己有没有好好上过课了。于是上我们的版本二：
find_routes <- function(n) {
x <- n
y <- n
cacheMat <- matrix(0, nrow=x+1, ncol=y+1)
cacheMat[1,] = 1
cacheMat[,1] = 1
for (i in2:(n+1)) {
for (j in2:(n+1)) {
cacheMat[i,j] <- cacheMat[i-1, j] + cacheMat[i, j-1]
}
}
return(cacheMat[n+1, n+1])
} 没有递归，没有缓存函数输出这些操作，代码又短又简单，而计算，也是瞬间的事情。