关于leetcode的一个小练习
思路: 使用二维数组来实现。规律为除了第一行和第一列全为1外,其他格的路径数为其上一格和左一格的和。
class Solution:
def uniquePaths(self, m, n):
paths = [[1] for i in range(m)] # initialize the 1st column to be 1
for i in range(n - 1): # initialize the 1st row to be 1
paths[0].append(1)
for i in range(m - 1):
for j in range(n - 1):
paths[i + 1].append(paths[i][j + 1] + paths[i + 1][j])
return paths[m - 1][n - 1]