首页 > 代码库 > leetcode-Uniqe Paths
leetcode-Uniqe Paths
题目
https://oj.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?
思路
每个到达终点的方案需要向右m-1步，向下n-1步，一共m+n-2步；
从组合角度，可以理解为从m+n-2中选择m-1步向右走，剩下n-1步向下走。
代码
1 class Solution:
2 # @return an integer
3 def uniquePaths(self, m, n):
4 return int(self.combination(m+n-2, n-1))
5
6 def combination(self, n, k):
7 res = 1.0
8 for i in range(1, k+1):
9 res = res * (n - k + i) / i
10 return res
2 # @return an integer
3 def uniquePaths(self, m, n):
4 return int(self.combination(m+n-2, n-1))
5
6 def combination(self, n, k):
7 res = 1.0
8 for i in range(1, k+1):
9 res = res * (n - k + i) / i
10 return res
参考地址
1. https://oj.leetcode.com/discuss/9110/my-ac-solution-using-formula
leetcode-Uniqe Paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。