class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m ==1 and n ==1:
return 1
self.res = 0
def getList(l,w):
if l == m and w == n:
self.res += 1
elif l < m and w < n:
getList(l+1,w)
getList(l,w+1)
elif l == m and w <n:
getList(l,w+1)
elif l < m and w == n:
getList(l+1,w)
getList(1,1)
return self.res
运行到 37/62 ，超时了，方法是对的应该还有更优解。
顶层：
l<m,w<n的时候，两边都可以递归
l ==m,只递归n边
w==n,只递归m边
底层：
到达(m,n)时，返回
法2： 数学排列组合 A（m+n-2）/A(m-1)/A(n-1) 不考虑，主要是来学动态规划
法3：动态规划：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
所以 先建造一个 二维数组：
dp = [ [1] * n] + [ [1] + [0] * (n-1) for _ in range(m-1) ]
然后怎么不断更新值呢： 用循环，对，就是循环，很简单明确的思路。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1]*n] + [[1] + [0]*(n-1) for _ in range(m-1)]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[-1][-1]
