动态规划-树形记忆递归

Question

关于这个问题：

考虑N格M中的昆虫。昆虫从左下角开始，(0，0)，并希望在右上角结束，(M-1，N1)。这种昆虫只能向右或向上移动。编写一个函数路径，该路径采用网格长度和宽度，并返回昆虫从一开始到目标可以采取的不同路径的数目。

​

​

例如，2×2网格共有两种方式让昆虫从一开始就移动到目标。对于3×3网格，昆虫有6条不同的路径(上面只显示了3条)。

以下是递归解决方案：

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))
}

随着氮的增加，以下是影响：

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

回溯可以应用于fibonacci问题，重用以前的计算，使用树递归。

回忆录这个路径问题有意义吗？重用以前的计算

(注意:这个问题是为了应用树递归的思想，正如前面提到的这里。)

Answer 1

这个问题是众所周知的，其解是(M+N2选择M1)或等价解(M+N2选择N1)。使用回忆录需要O(NM)时间有意义吗？不完全是这样，因为二项式系数可以用相对简单的代码在O(min(M，N))时间(算术运算)中计算。

例如(操场链接)：

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))
    }
}

Answer 2

是的，可以用回忆录。要做的一个关键观察是考虑3x3网格中的网格(1，1)：

(2，0) (2，1) (2，2)

(1，0) (1，1) (1，2)

(0，0) (0，1) (0，2)

网格(1，1)中的路径数等于来自(1，0)的路径数加上(0，1)的路径数，因为只有两种可能的方法可以到达路径(1，1)。

概括：

npath(x，y) = npath(x-1，y) + npath(x，y-1)

其中npath(x，y) =访问网格(x，y)的可能路径数。

因此，如果向后构建递归，则可以应用回忆录。我的意思是，您必须从较小的情况开始，其中npath(_，0) = 1，npath(0，_) =1，下划线表示任何值。

该算法的简单运行将导致3x3网格中的路径数：

1 3 6

1 2 3

1 1 1

实际上，您可以只执行一个双嵌套循环，而不是作为优化的递归。