题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

思路

这里说两种解法：

1、数学思维，排列组合

一共需要走m + n - 2步，其中，m - 1 往右，所以问题转化为求如下图中式子的值：

2、动态规划

初始第一行全为1，第二行第一个为1，意指到达这些位置的路径只有一种，然后第二行 i 位置的数据由第一行 i 位置的路径数 + 第二行 i-1位置的路径数获得

代码

排列组合

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        n,m=max(m,n),min(m,n)
        
        mult_1=1
        for i in range(n,n+m-1):
            mult_1*=i
        mult_2=1
        for i in range(1,m):
            mult_2*=i
            
        return int(mult_1/mult_2)

动态规划

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row1 = [1 for i in range(m)]
        row_num=1
        while(row_num<n):
            row2 = [1]
            for i in range(1,m):
                row2.append(row2[i-1]+ row1[i])
            row1 = row2
            row_num+=1
        return row1[-1]

---

欢迎大家关注我的公众号

半亩房顶