LeetCode 双刀流：62. Unique Paths

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 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。