数学方法

只能右下，那么往右一共是m-1，往下一共走n-1次，一共会走m-1+n-1次。
可以理解为要走m+n-1次，要选择m-1次右（或者n-1次下），也就是$C_{m+n-2}^{n-1}$。

import math
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return math.comb(m+n-2,m-1) # math.comb(m+n-2,n-1)也行，一样，组合的性质。
1
2
3
4

深度优先搜索

当然除了数学方法，自然是暴力搜索了

import math
class Solution:
    def find(self,y,x):  
        if y==1 and x==1:
            self.how_many+=1
        if x>1:
            self.find(y,x-1)
        if y>1:
            self.find(y-1,x)
        return

    def uniquePaths(self, m: int, n: int) -> int:
        self.how_many=0

        self.find(m,n)
        return self.how_many
            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

果然time limit了，37 / 63 个通过测试用例。
没关系，我们再试一下动态规划。

动态规划

自然是dfs的逆思维。
首先定义成迭代问题，用$T(i,j)$表示到达坐标i,j的路线数，则状态转移方程是：
$$T(i,j)=T(i-1,j)+T(i,j-1)$$
就是说，能达到我i j这个位置的要么从上方来，要么从左侧来。到达我上方的路原本a次，到达我左侧的原本有b次，那到达我这里的路应当是a+b次。

然后迭代从小规模做起。
然后自己验证一下，可以自己画个表格，从0 0位置填起，发现最上面一横行和最左侧一竖列都是1的，因为只能连续向右走或者向下走，可以直接初始化。
其他的就没啥了。

class Solution:
    
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[[0 for _ in range(n)] for _ in range(m)]
        for i in range(n):
            dp[0][i]=1 
        for i in range(m):
            dp[i][0]=1 

        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
                
        
        # print(dp)
        return dp[-1][-1]  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提交一下就过了。