LeetCode刷题实战62：不同路径
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 不同路径，我们先来看题面：
https://leetcode-cn.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?
题意
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
解题
解法
dp[i][j] = dp[i-1][j] + dp[i][j-1]
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n+2)] for _ in range(m+2)]
dp[0][1] = 1
for i in range(1, m+1):
# 特殊处理第一列，因为第一列只有1种
dp[i][1] = dp[i-1][1]
for j in range(2, n+1):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m][n]
one more solution
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
ret = 1
for i in range(1, n):
ret = ret * (n+m-1-i) // i
return ret
的算法，好像差别不大。但是每个数的阶乘和组合数都是可以预处理的，在频繁求解的场景下，显然要比动态规划算法更快。上期推文：
评论