0062. Unique Paths (Medium)

Question

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?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1

1
2
3
4
5
6
7

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2

1
2

Input: m = 7, n = 3
Output: 28

分析/解題

有一個m x n大小的格子，其左上處有一台機器人，每次機器人僅能選擇往右或往下走，目的是要達到右下角的Finish的位置，題目問說當給定m和n時，有多少種不同的方法可以從左上走到右下？

這題也是典型的動態規劃題目，只要稍稍思考一下，
我們就能發現一件事情：
走到任何一個點的方式，取決於走到其左的方法數 加上走到其上的方法數 。

那麼，再思考一下走到左邊跟走到上面會有重複的狀況嗎？顯然是不會的。
因為走到一個格子的左邊顯然和走到其上面會相差往下走一格及往右走一格的動作，而且因為機器人也只能往下或往右，所以沒辦法再回頭，故已經走過的部分不可能再繞得回來。

在這個狀況的特例有幾個：

1. 機器人所站的原點 (按我們的定義一開始就在此，故可以將方法數定為1)
2. 最左邊 的一排格子 (僅取決於走到其上面格子的方法數)
3. 最上面 的一排格子 (僅取決於走到其左邊格子的方法數)

而實際上從第1點來推算的話，
我們可以知道最左邊一排跟最上面到達的方法數都會是1 。
所以我們可以先將這三點的部分先設定為1，接著從較小的index開始沿途把到達每個點的方法算出來，直到最後將整個grid算完。

在這個方法下，我們需要一個m x n的陣列用以儲存方法數，為了方便起見，我們就直接叫它dp，讀者亦可命名為grid，請留意這些命名都只是方便起見，只要你的命名能和面試官溝通即可，我們現在並不是在寫一個大的project，簡短命名並告知你的面試官你的目的是筆者推薦的做法。

最後僅需回傳dp[m-1][n-1]即可。
(註:由於這邊row跟column的交換並不影響結果，
故我們這邊不特別去在意m和n的前後順序。)

Java

Python這邊收尾的時候可以用dp[-1][-1]來表示尾端的元素，
宣告的時候則採用list comprehension(列表解析式/列表表達式)。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(均為O(m*n))

「空間複雜度是否可以降低？」
(理論上可以，因為實際每次處理的關連部分僅有兩行或兩列，
反覆利用應該可以讓空間需求降低到O(m)或O(n)，但時間複雜度一致)

「是否有更簡單的解？」
(DP的話，沒有，數學的話，有。
 假設往下叫D，往右叫R，求不同走法的過程，
即相當於在求**(n-1)個D和(m-1)個R的不同排列方法** ，
故答案會是(m-1+n-1)!/(m-1)!(n-1)!，
此時空間複雜度為O(1)，時間複雜度為O(m+n) 。
但階乘的部分當值過大時有可能會有超過int的可能性。)

從LeetCode學演算法，我們下次見囉，掰~