62. Unique Paths

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?

再搭配範例理解題目

• Example 1:

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

• Example 2:

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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

這個題目要計算在一個方格地圖當中，機器人從左上角開始只可以往右方或下方移動，而到達其中一個格子的可能路徑有幾次。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：暴力遞迴法

根據觀察會發現，每一格只會來自於「上方」或是「左方」，也就是說「每一個格子的路徑」的可能就會等於「上方格子的路徑」+「左方格子的路徑」，會呈現一個由左上到右下遞增的結果。而這個過程，其實很直覺就會想到用遞迴的方法，將「每一個格子的路徑」轉化成「上方格子」與「左方格子」遞迴計算。

用 Python 實作一次

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return self.findPath(m, n, 1, 1)

    def findPath(self, m, n, row, col):
        if row == m and col == n: return 1
        if row > m or col > n: return 0
        return self.findPath(m, n, row, col + 1) + self.findPath(m, n, row + 1, col)

也可以用 JavaScript 復刻一次

var uniquePaths = function(m, n) {
    return findPath(m, n, 1, 1);
};

const findPath = (m, n, row, col) => {
  if(row === m && col === n) return 1;
  if(row > m || col > n) return 0;
  return findPath(m, n, row, col + 1) + findPath(m, n, row + 1, col);
};

不過這種方法會出現「**Time Limit Exceeded **」，原因是在遞迴過程中太過耗時了。

方法 ②：遞迴法 + Hashmap

仔細想了一下，第一種方法會失敗的原因是主要是在計算每個格子的時候都需要遞迴到最邊緣的點才會終止。這個會造成不大量的重複計算，方法二我們可以將計算的過程儲存到 Hashmap 當中，只要有計算過的點就不需要重複計算。

用 Python 實作一次

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        d = {}
        return self.findPath(m, n, d)

    def findPath(self, m, n, d):
        if (m, n) in d: return d[(m, n)]
        if m == 1 or n == 1: return 1
        d[(m, n)] = self.findPath(m - 1, n, d) + self.findPath(m, n - 1, d)
        return d[(m, n)]

也可以用 JavaScript 復刻一次

var uniquePaths = function(m, n) {
  let d = {}
  return findPath(m, n, d)
    
  function findPath(m, n, d){
    if (d[`${m}-${n}` > 0]) return d[`${m}-${m}`]
    if (m == 1 || n == 1) return 1
    d[`${m}-${n}`] = findPath(m - 1, n, d) + findPath(m, n - 1, d)
    return d[`${m}-${n}`]
  }
};

方法 ③：動態規劃法

第三種方法可以想成是方法二的加強版，方法二使用 Hashmap 暫存遞迴的計算過程。方法三我們進一步使用一個陣列來儲存累加的過程，把每一個格子的路徑數量都記錄下來。換句話說，就是把遞迴的過程直接利用資料結構來儲存，其實就是所謂的「動態規劃法」。

用 Python 實作一次

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

也可以用 JavaScript 復刻一次

var uniquePaths = function(m, n) {
  let d = new Array(m+1).fill(1).map(x => new Array(n+1).fill(0));
  for (let i=1;i<=m;i++) {
    for (let j=1;j<=n;j++) {
      if (i==1 && j==1) 
        d[i][j] = 1;
      else 
        d[i][j] = d[i-1][j] + d[i][j-1];
      }
    }
    return d[m][n];
}

反思沉澱

這兩天的題目都在嘗試動態規劃的問題，例如昨天的「爬第 n 階樓梯的方法數」與今天的「移動到 m, n 格子的路徑數」，都是可以同時使用到「遞迴」與「動態規劃」兩種解法。就如同我們前面有說「動態規劃」跟「遞迴」其實只有一線之隔，依循著「窮舉」→「遞迴」→「動態規劃」的優化過程，搞懂了遞迴、動態規劃自然實現了！動態規劃沒有那麼難，學習起來就是這麼樸實。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 63. Unique Paths II
• 64. Minimum Path Sum

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。