木又同学2020年第28篇解题报告
leetcode第62题:不同路径
https://leetcode-cn.com/problems/unique-paths/
【题目】
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?
说明:m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
【思路】
这是一道典型的排列组合题,机器人走到右下角,需要向下走m-1步,向右走n-1步,那么唯一路径的总数为(m - 1 + n - 1)! / ((m - 1)! * (n - 1)!)。
【代码】
python版本
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
# 排列组合问题
# 实际上,向下走m-1步,向右走n-1步
# (m+n-2)! / ((m-1)! * (n-1)!)
res = 1
for i in range(m, m + n - 1):
res *= i
for i in range(1, n):
res /= i
return res
C++版本
class Solution {
public:
int uniquePaths(int m, int n) {
// 总步数 m+n-2
double res = 1;
if(m < n){
int tmp = m;
m = n;
n = tmp;
}
for(int i=m, j=1; i<m+n-1; i++, j++){
res *= i;
if(j < n)
res /= j;
}
return res;
}
};