妈呀 这62，78，89三道题都是一模一样的做法感觉：

　　62：长度一定的路径，每一步选择 向右 或向下  （递归顺序无关）

　　78：长度一定的列表，每一个元素选择 放入或不放入 （递归顺序无关）

　　89：长度都为n，上次加入的元素为0 就先递归0 再递归1； 上次加入的元素为1，就先递归1 后递归0。

 

　　OK，先去写了。

递归法：

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]