如何在Python中记忆唯一路径的解决方案

Question

我试图解决这个问题已经有一段时间了。给出了一个M×N网格，我们必须找到从左上角到右下角的路径数。

不过问题很简单；也有很多解决方案。这是细节。http://www.interviewbit.com/courses/programming/topics/math/problems/paths/http://articles.leetcode.com/2010/11/unique-paths.html

我用Java解决了这个问题，并用Python编写了另一个解决方案。现在我想用记忆表格修改之前的解决方案，以便在右下角的单元格中收集最终答案。单元格的值是其左右相邻单元格的总和。

这是我无法调试的代码：-

class Solution:
    #Actual Recursive function
    def paths(self,row,col):
        if row == 0 or col == 0:
            self.Mat[row][col] = 1
            return 1
        self.Mat[row][col-1] = self.paths(row, col-1)
        self.Mat[row-1][col] = self.paths(row-1, col)
        self.Mat[row][col] = self.Mat[row][col-1] + self.Mat[row-1][col]
        return self.Mat[row][col] 

    # Driver Function. This will be called
    def uniquePaths(self, A, B): 
        self.Mat = [[-1]*B]*A
        ans = self.paths(A-1, B-1)
        return self.Mat[A-1][B-1]

这是我以前的解决方案，它可以工作，但不使用记忆表。

class OldSolution:
    def paths(self,row,col):
        if row==0 or col==0:
            return 1
        elif row<0 or col<0:
            return 0
        elif row >0 and col > 0:
            return self.paths(row-1,col) + self.paths(row,col-1)            
    def uniquePaths(self, A, B):
        Mat = [ [-1] * B ] *A
        return self.paths(A-1, B-1)

sol = OldSolution()
print sol.uniquePaths(3,3) # Prints 6

测试用例：-3,3=6

15, 9 = 319770

Answer 1

问题在于矩阵的初始化。实际上，您在每一列中创建了相同的重复行，因此当您更新单元格时，所有列中的所有对应单元格都会得到更新。

而不是：

self.Mat = [[-1]*B]*A

使用：

self.Mat = [[-1 for i in range(B)] for j in range(A)]