algorithm - How to Memoize the solution to Unique Paths in Python -

i've been trying solve problem while. m x n grid given , we've find number paths top left corner bottom right corner.

simple problem though; there many solutions well. here're details. http://www.interviewbit.com/courses/programming/topics/math/problems/paths/ http://articles.leetcode.com/2010/11/unique-paths.html

i solved problem in java, , wrote 1 more solution in python. want modify previous solution memoized table final answer gets collected @ bottom right cell. value of cell sum of right , left adjacent cells.

here's code can't debug:-

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. 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] 

and here previous solution works - doesn't use 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 , 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 

test cases:- 3, 3 = 6

15, 9 = 319770

the issue initialization of matrix. create same row duplicated in every column when update cell, corresponding cells in columns updated.

instead of:

self.mat = [[-1]*b]*a 

use:

self.mat = [[-1 in range(b)] j in range(a)]