如何在 Python 中记忆唯一路径的解决方案
How to Memoize the solution to Unique Paths in Python
我已经尝试解决这个问题一段时间了。给定一个 M x N 网格,我们必须找到从左上角到右下角的路径数。
虽然问题很简单;也有很多解决方案。这是详细信息。
http://www.interviewbit.com/courses/programming/topics/math/problems/paths/
http://articles.leetcode.com/2010/11/unique-paths.html
我在 Java 中解决了这个问题,并在 Python 中写了一个解决方案。现在我想用 Memoized table 修改以前的解决方案,以便最终答案收集在右下角的单元格中。单元格的值是其左右相邻单元格的总和。
这是我无法调试的代码:-
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]
这是我以前的有效解决方案 - 但不使用 memoized table。
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
问题出在矩阵的初始化上。您基本上在每一列中创建了相同的行,因此当您更新单元格时,所有列中的所有对应单元格都会更新。
而不是:
self.Mat = [[-1]*B]*A
使用:
self.Mat = [[-1 for i in range(B)] for j in range(A)]
我已经尝试解决这个问题一段时间了。给定一个 M x N 网格,我们必须找到从左上角到右下角的路径数。
虽然问题很简单;也有很多解决方案。这是详细信息。 http://www.interviewbit.com/courses/programming/topics/math/problems/paths/ http://articles.leetcode.com/2010/11/unique-paths.html
我在 Java 中解决了这个问题,并在 Python 中写了一个解决方案。现在我想用 Memoized table 修改以前的解决方案,以便最终答案收集在右下角的单元格中。单元格的值是其左右相邻单元格的总和。
这是我无法调试的代码:-
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]
这是我以前的有效解决方案 - 但不使用 memoized table。
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
问题出在矩阵的初始化上。您基本上在每一列中创建了相同的行,因此当您更新单元格时,所有列中的所有对应单元格都会更新。
而不是:
self.Mat = [[-1]*B]*A
使用:
self.Mat = [[-1 for i in range(B)] for j in range(A)]