python中的递归与多维矩阵

Question

这是著名的路径计数问题，我试图用记忆来解决它。 开导我！在

def pathCounter(a,b):
    matrix = [[0 for i in xrange(a)] for i in xrange(b)]

    if a==0 or b==0:
        return 1

    if matrix[a][b]:
        return matrix[a][b]

    print matrix[a][b]
    matrix[a][b]=pathCounter(a,b-1)+pathCounter(a-1,b)

    return matrix[2][2] 

if __name__=='__main__':
    k=pathCounter(2,2)
    print k

Answer 1

我相信你想解决this problem

如果是这样，那么您是正确的，它将是明智的解决递归。在

如果您将网格的每个角落想象为一个节点，那么您需要一个递归函数，它只需接受它所在节点的参数{}。在函数中，它首先需要检查调用它的位置是否是网格的右下角顶点。如果是，函数会将一个添加到path count（当路径到达这个角时，路径就结束了），然后返回。否则，这个函数只调用另外两个自身（这是递归），一个调用它的right（soy+1），另一个调用它的left（x+1）。另外一个步骤是检查坐标是否在网格中，然后将其作为最下面一行中间的节点调用，例如不应该调用它下面的节点，因为那样会脱离网格。在

现在已经定义了递归函数，现在只需声明一个变量来存储path count。并从坐标（0,0）调用递归函数。在

但是，正如我确信您已经看到的，这个解决方案并没有在合理的时间内完成，所以您有必要使用memoization-通过缓存节点来加速它，这样相同的路径部分不会被计算两次。在

如果像您所做的那样，我们从右下角向上到左上角工作，这也使编码变得更加简单。最后一件事是，如果使用dictionary，那么代码会变得更清晰。在

最后的代码应该类似于：

cache = {}

def pathCounter(x, y):
   if x == 0 or y == 0:
       return 1
   if (x,y) in cache:
      return cache[(x,y)]

   cache[(x,y)] = pathCounter(x, y-1) + pathCounter(x-1, y)
   return cache[(x,y)]

print(pathCounter(2,2))

这将得到6的预期结果。在

我让你来做20x20网格。希望这有帮助！在

Answer 2

你在算法的实现中犯了一些错误。如果使用递归方法，则不必使用grid，因为实际上您需要任何存储的数据。你只需要从当前位置返回两个可能的子路径-就这样！因此，您需要对代码的主要思想进行一些更改。在

我尽量保留您的原始代码，但仍能正常工作：

def pathCounterNaive(width, height, startX = 0, startY = 0):
    if startX >= width or startY >= height:
       return 0

   if startX == width-1 and startY == height-1:
      return 1

   return pathCounter(width,height, startX+1, startY) + pathCounter(width,height, startX, startY+1)

slowK=pathCounterNaive(3,3)
print(slowK)

请记住，参数width和height表示顶点的数目，因此对于2x2网格，它们不是2，而是3。由于这段代码使用纯递归，所以速度非常慢。如果你想使用你的记忆方法，你必须修改你的代码如下：

^{pr2}$

这里您必须使用2作为2x2网格的参数来调用它。由于缓存了已计算的路径，此代码要快得多。在