【Leetcode解題】62. Unique Paths

題目

• 題目連結

解題概念

• 此題講白了，就是要運用排列組合中的不盡相異物直線排列
  • 原理 : 可參考此網頁
  • 公式 :
    • 假設總共有 $n$ 個元素，可分為 $k$ 組，且每組有 $m_i$ 個元素，則方法數為 $$\frac{n!}{m_1!m_2!\cdots m_k!}$$
• 套用在此題中，則可視為把 $m-1$ 個 Right 與 $n-1$ 個 Down 做不盡相異物直線排列 :
  1. Right 有 m - 1 個
  2. Down 有 n - 1 個
  3. 總元素 Total 有 right + down 個
  4. 因此，可推論出此題的解法為$$\frac{\text{Total}!}{\text{Right}!\text{ }\text{Down}!}$$

實際寫Code

• 目標函式 : uniquePaths(m, n)
  • Input : m: int、n: int
  • Output : int
• 主要程式碼 :

  right = m - 1
  down = n - 1
  total = right + down
  return math.factorial(total) / (math.factorial(right) * math.factorial(down))

參考資料

1. 不盡相異物直線排列與重複排列