[LeetCode]题解（python）：062 Unique path

题目来源

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）

 1 __author__ = 'YE'
 2 
 3 class Solution(object):
 4     def uniquePaths(self, m, n):
 5         """
 6         :type m: int
 7         :type n: int
 8         :rtype: int
 9         """
10         def fac(n):
11             f = 1
12             for i in range(1, n + 1):
13                 f *= i
14             return f
15 
16         m -= 1
17         n -= 1
18         if m == 0 or n == 0:
19             return 1
20         return fac(m + n) / (fac(m) * fac(n))
21 
22 print(Solution().uniquePaths(3, 7))

[LeetCode]题解（python）：062 Unique path

相关推荐