A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Solution:
In order to obtain O(n) we just keep the last row and the actual oneclass Solution: # @return an integer def uniquePaths(self, m, n): for row in range(0,m): actualRow = [] for col in range(0,n): if row ==0 and col==0: actual = 1 else: actual = 0; if row>0: actual += previousRow[col] if col>0: actual += actualRow[col-1] actualRow.append(actual) previousRow= actualRow return actualRow[n-1]
No comments :
Post a Comment