[LeetCode]题解(python):062 Unique path

时间:2022-04-07 19:16:47

题目来源


https://leetcode.com/problems/unique-paths/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?


题意分析


Input:m、n

Output:the number of unique path

Conditions:输出所有可能的路径


题目思路


一看想起了全排列,注意到(m=3,n=7)时,表示要向下2步向右6步,那么全排列可得路径为f(2+6)/(f(2)*f(6)),f为阶乘函数


AC代码(Python)


 __author__ = 'YE'

 class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
def fac(n):
f = 1
for i in range(1, n + 1):
f *= i
return f m -= 1
n -= 1
if m == 0 or n == 0:
return 1
return fac(m + n) / (fac(m) * fac(n)) print(Solution().uniquePaths(3, 7))