土豆炒青椒
土豆炒青椒

「谷歌」圣诞夜 刷 62 ~ 独立的路径

过节也要完成每日刷题任务

基本信息

  • 题号:62
  • 题厂:谷歌
  • 难度系数:中



已知一个矩阵,问从起点到终点,一共有几种走法?即图中,粉红机器人走到 finish 星星处,一共有几种不同走法???

例如 m = 3, n = 7
返回 28 —— 种


解题思路

  • 机器人只能横走或竖走,即每一次,机器人有两种走法——那我直接写个 recursive 把所有走法遍历出来就好……
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 当走到头时,即当前 index 均为 0 时,为一个完整路径走法,返回 path + 1
        # 如果还没有,那就有两种走法,向下或向右,分别recursive 直到头
        def dfs(down, right, path):
            if down == 0 or right == 0:
                return path + 1
            
            return dfs(down - 1, right, path) + dfs(down, right - 1, path)
        
        return dfs(m - 1, n - 1, 0)


  • 以上代码虽然看起来简洁,但是计算了很多次,是明显会超时的。为了减少冗余的计算,程序届闻风丧胆的动态规划(dynamic programming)闪亮登场了……😭
  • 动态规划的思路核心是,一个复杂的结果根植于简单的结果从 1 或 0 开始逐步推导
  • 本题中,我们需要倒推思考:
  1. 如果棋盘只有一个 1 X 1,我们只有一种走法
  2. 如果棋盘是 2 X 1 或 1 X 2,我们还是只有一种走法,从右往左走,或从下往上走
  3. 如果棋盘是 2 X 2,我们有了 2 种不同走法,这两种不同走法分别由 2 X 1 和 1 X 2 贡献累加……
  4. 于是我们推导出:每一个格子的走法 = 左边格子走法 + 右边格子走法


  • 让以上思路通过代码实现,我们创建一个与棋盘宽相等的数组 row,初始值为 1。当棋盘为 1 X n,无论 n 取何值,每个格子始终只有一种走法,即向右走……
  • 遍历时更新累加值,返回值即 row 的第一个元素

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


Constraints

1 <= m, n <= 100



测试

  • 棋盘 1 X 1
  • 1 X n 只有一行时
  • n X 1 只有一列时
  • 100 X 100 取最大值,检验算法有效度
  • ……




Big O

  • 时间复杂度:O(n X m), 遍历了每一个格子
  • 空间复杂度:O(n),创建了长度为 n 的 row 变量




总结

  • 考试时遇上,一时想不出动态编程代码,就把 recursive 方法拿去和考官讨论。有解法总比没有强。
  • 动态编程困难点有 2: 
  1. 如何找到规律 pattern
  2. 发现规律后,如何用代码实现此规律解决问题
  • 考试时,一时紧张可能很难 40 分钟完成一道动态编程题,但是动态编程系列题模板规律还是挺强的,也就只能熟能生巧解决了……😭


CC BY-NC-ND 2.0 版权声明

喜欢我的文章吗?
别忘了给点支持与赞赏,让我知道创作的路上有你陪伴。

加载中…

发布评论