有一個機器人的位于一個 m × n 個網格左上角。

機器人每一時刻只能向下或者向右移動一步。機器人試圖達到網格的右下角。

問有多少條不同的路徑？

n和m均不超過100
且答案保證在32位整數可表示范圍內。

樣例
Example 1:

Input: n = 1, m = 3
Output: 1

思路

從數學的角度考慮， 機器人一共需要向兩個方向各走 m - 1, n - 1 步，即總共要走m + n - 2步，選取其中的m - 1步往右走即可。

所以答案就是

class Solution(object):def uniquePaths(self, m, n):""":type m: int:type n: int:rtype: int"""# C(m + n - 2) (m - 1)k = m + n - 2t = m - 1right = 1for i in range(0, t):left *= k - i#m - 1的階乘down = 1for i in range(1, m):down *= i#(m + n - 2)的階乘# print right, downreturn right // down c=Solution() d=c.uniquePaths(4,3) print(d)

結果 10

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的LeetCode114. 不同的路径 python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。