iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 22
1
Software Development

從LeetCode學演算法系列 第 22

[Day 22] 從LeetCode學演算法 - 0062. Unique Paths (Medium)

目標:
這題主要目的在於進一步講解需要二維陣列輔助解的DP問題。

原題:

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:
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:
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:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

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

Python:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(均為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學演算法,我們下次見囉,掰~

下篇預告:
0169. Majority Element (Easy)


上一篇
[Day 21] 從LeetCode學演算法 - 0110. Balanced Binary Tree (Easy)
下一篇
[Day 23] 從LeetCode學演算法 - 0169. Majority Element (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言