hash 微信公众号开发 vue组件 less 分布式服务 excel xcode multithreading browser angular ui router odbc vue路由 vue源码下载 vue优势 vue配置 idea格式化代码设置 数据库查询 python异常 python中的join函数 python获取字典的值 python搭建网站 java抽象 java多态 java怎么输出数组 java语言编程 java删除数组中的某个元素 电池救星 数据库系统概论第五版 js获取父节点 maya2008 全英雄守城战 掌门一对一下载 list删除指定元素 php递归 抠图教程 android下载文件 商标查询软件 如何查看端口是否开放 cad如何旋转图形 金万维动态域名
当前位置: 首页 > 学习教程  > python

【Leetcode】62. 不同路径(Unique Paths)

2021/2/8 12:15:05 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No62. 不同路径 题目 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路…

No62. 不同路径

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例1

在这里插入图片描述

  • 输入:m = 3, n = 7
  • 输出:28

示例2

  • 输入:m = 3, n = 2
  • 输出:3
  • 解释:
    从左上角开始,总共有 3 条路径可以到达右下角。
  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例3

输入:m = 7, n = 3
输出:28

示例4

输入:m = 3, n = 3
输出:6

思路:

用数组去存储到每个方块的可能路径数,由于规则限定,左侧和上侧的每个方块可能经过的路径均为1。

更一般地,由于每个方块的可能路径数可以用左侧和上侧的和来表示,所以可以利用迭代思想只用last和now两个长为n的List去存储可能路径数。

解题代码(Python3)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        last = [1]*n
        now = [1]*n
        for index in range(1,m):
            for col in range(1,n):
                temp = now
                now[col] = now[col - 1] + last[col]
                last = temp
        return now[-1]

复杂度分析:

  • 时间复杂度O(m*n)
  • 空间复杂度O(n) 额外2个长为n的辅助空间

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000318.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?