?LeetCode刷題實戰(zhàn)62：不同路徑
算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從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
的算法，好像差別不大。但是每個數(shù)的階乘和組合數(shù)都是可以預處理的，在頻繁求解的場景下，顯然要比動態(tài)規(guī)劃算法更快。上期推文：
評論
圖片
表情