go - 动态编程-带内存的树递归

Question

对于问题:

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal.

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

以下是递归解决方案:

package main

import "fmt"

func paths(m, n int) int {

    var traverse func(int, int) int
    traverse = func(x, y int) int {

        if x >= m || y >= n {
            return 0
        }
        if x == m-1 && y == n-1 {
            return 1
        }
        return traverse(x+1, y) + traverse(x, y+1)
    }
    return traverse(0, 0)
}

func main() {
    fmt.Println(paths(1, 157))
}

随着N的增加，效果如下:

fmt.Println(paths(1, 1)) // 1
fmt.Println(paths(2, 2)) // 2
fmt.Println(paths(3, 3)) // 6
fmt.Println(paths(4, 4)) // 20
fmt.Println(paths(5, 5)) // 70
fmt.Println(paths(6, 6)) // 252
fmt.Println(paths(7, 7)) // 924

可以在斐波纳契问题中应用内存，使用树递归来重用以前的计算
记住这个路径问题有意义吗？重用以前的计算
(注意:这个问题是为了应用here所提到的树递归的想法。)

Answer 1

该问题是众所周知的，并且具有(M + N-2选择M-1)或等效的解决方案(M + N-2选择N-1)。使用需要O(NM)时间的内存是否有意义？并非如此，因为可以用相对简单的代码在O(min(M，N))时间(算术运算)中计算二项式系数。
例如(playground link):

package main

import (
    "fmt"
    "math/big"
)

func paths(n, m int) *big.Int {
    return big.NewInt(0).Binomial(int64(n+m-2), int64(m-1))
}

func main() {
    for i := 1; i < 10; i++ {
        fmt.Println(i, paths(i, i))
    }
}