62. 不同路径
62. 不同路径
一个机器人位于一个 m∗nm * nm∗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 <= m, n <= 100
- 题目数据保证答案小于等于 2∗1092 * 10^92∗109
思路:(动态规划)
由于每次只能向下或者向右移动,所以到达任意一个位置,不是从上面到达就是从左边到达,从而到达该位置的路径就是这两个方向之和:
- 定义一个 m*n 矩阵dp,用于存放到达当前位置的所有路径;
- 第一列和第一行比较特殊,分别只能从上方到达,从左面到达,因此只用一条路,赋值为1;
- 其余位置要比较从左面,从上面到达,所以动态方程为:dp[i][j] = dp[i-1][j] + dp[i][j-1]
代码:(Java)
public class difPath {public static void main(String[] args) {// TODO Auto-generated method stubint m = 3, n = 7; System.out.println(uniquePaths(m, n));}public static 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 j = 0; j < n; j++) {dp[0][j] = 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];}
}
运行结果:

复杂度分析:
时间复杂度:O(m∗n) 。
空间复杂度:O(m∗n) 。(优化:因为我们每次只需要 dp[i-1][j],dp[i][j-1],所以我们只要记录这两个数,所以空间复杂度可以为 :O(1) . )
注:仅供学习参考!
题目来源:力扣。
相关文章:
62. 不同路径
62. 不同路径 一个机器人位于一个 m∗nm * nm∗n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路…...
在windows安装python3.11同时进行一个数据的练习
安装包百度网盘如下: 链接:https://pan.baidu.com/s/1l9H1GWP64LOxLaXXLie2uA?pwd6666 提取码:6666 1.我们选择自定义安装 2.当我们点了自定义安装后就直接next 3.修改路径,之后点击安装(install) 4.安装完成,进行…...
Java接口专题
基本介绍 接口给出一些没有实现的方法,封装到一起,到某个类使用时再根据具体情况把这些方法写出来。 注意:在jdk7之前,接口里所有的方法都是抽象方法。在jdk8之后接口中可以有静态方法,默认方法 interface 接口名{/…...
6招优化WordPress打开速度-让你的网站飞起来
为什么我们的WordPress网站比你的快? 我们的官网是使用WordPress框架搭建的,有没有发现我们的网站非常快,而你的WordPress网站比较慢呢?那是因为我们的网站经过了优化。 WordPress 很慢? 为什么很多人都会觉得 Word…...
春天到了,来一场 VoxEdit 创作大赛吧!
春天的气息扑面而来,这是让你尽情绽放创造力的最佳时机!我们将以「春天」为主题来一场 VoxEdit 大赛。在这里,你可以展示你的才华并赢得 $SAND 奖励! 无论你是专业的设计师,还是仅仅喜欢创造美丽的艺术,这场…...
异步Buck和同步Buck的特点
1 介绍 随着时代的发展,工业,车载,通信,消费类等产品都提出了小型化,智能化的需求。相应的,对于这些系统中的电源模块提出了小型化的要求。目前,市场上依然存在很多异步Buck电源管理芯片使用的场…...
基于轻量级YOLO开发构建中国象棋目标检测识别分析系统
关于棋类相关的项目在我之前的博文里面都有做过,如下:《yolov5s融合SPD-Conv用于提升小目标和低分辨率图像检测性能实践五子棋检测识别》《YOLOV5融合SE注意力机制和SwinTransformer模块开发实践的中国象棋检测识别分析系统》《基于yolov5s实践国际象棋目…...
机器学习100天(三十五):035 贝叶斯公式
《机器学习100天》完整目录:目录 机器学习100天,今天讲的是:贝叶斯公式! 好了,上一节介绍完先验概率、后验概率、联合概率、全概率后,我们来看这样一个问题:如果我现在挑到了一个瓜蒂脱落的瓜,则该瓜是好瓜的概率多大? 显然,这是一个计算后验概率的问题,根据我们之…...
大话数据结构-栈
1 概述 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。 允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈,栈又称为后进…...
javaFx实现放大镜效果——圆形、矩形、三角形放大镜,拖动调整放大镜大小,设置放大倍数
系列文章专栏:javafx图形绘制、桌面录屏录音源码合集 目录 一、实现的效果 二、实现思路 三、程序实现...
什么是客户忠诚度?建立忠诚文化的 5 种方法
客户忠诚度影响企业的各个方面,例如收入、品牌形象、预算分配和产品路线图。拥有忠实的客户群对于建立成功的企业至关重要,因为您的客户是您的主要拥护者,有助于为您的企业营造积极的氛围。 什么是客户忠诚度? 客户忠诚度衡量客户…...
【ROS2知识】关于colcon编译和ament指定
一、说明 这里说说编译和包生成的操作要点,以python包为例。对于初学者来说,colcon和ament需要概念上搞清楚,与此同时,工作空间、包、节点在一个工程中需要熟练掌握。本文以humble版的ROS2,进行python编程的实现。 二、…...
数据结构: 最小栈
最小栈的特色是保持栈后进先出的特性,同时能够以O(1)复杂度获得当前栈的最小值。 栈是比较好实现的,直接搞个链表,从头部删除和添加即可。 最小栈的核心逻辑是: 因为栈是后进先出的,因此栈顶元素之下的数字永远在栈…...
STM32之PWM
PWMPWM,英文名Pulse Width Modulation,是脉冲宽度调制缩写,它是通过对一系列脉冲的宽度进行调制,等效出所需要的波形(包含形状以及幅值),对模拟信号电平进行数字编码,也就是说通过调…...
操作系统(1.1)--引论
目录 一、操作系统的目标和作用 1.操作系统的目标 2.操作系统的作用 2.1 OS作为用户与计算机硬件系统之间的接口 2.2 OS作为计算机系统资源的管理者 2.3 0S实现了对计算机资源的抽象 3. 推动操作系统发展的主要动力 二、操作系统的发展过程 1.无操作系统的计算机系统…...
Spring boot + mybatis-plus 遇到 数据库字段 创建不规范 大驼峰 下划线 导致前端传参数 后端收不到参数 解决方案
最近使用springboot 连接了一个 sqlserver 数据库 由于数据库年数久远 ,建表字段不规范 大驼峰 下划线的字段名都有 但是 java 中 Spring boot mybatis-plus 又严格按照小驼峰 格式 生成实体类 如果不是小驼峰格式 Data 注解 get set 方法 在前端请求参数 使用这个…...
JavaScript String 字符串对象
文章目录JavaScript String 字符串对象JavaScript 字符串字符串(String)在字符串中查找字符串内容匹配替换内容字符串大小写转换字符串转为数组特殊字符字符串属性和方法JavaScript String 字符串对象 String 对象用于处理已有的字符块。 JavaScript 字…...
Lazada如何做好店铺运营?产品定价是关键
1.东南亚各国状况一览(对比中国) 2.东南亚消费水平真的很低? 精准定价的意义:定价过高,失去核心竞争力;定价过低,亏本对市场失去信心;价格改动,流量下降 定价公式&#…...
空口协议Eapol、802.11 Action、802.11 BAR 和 802.11BA、802.11 Encrypted Data讲解
如下报文 可以看到,除了有之前开放认证的报文之外,还多了 EAPOL 次握手的报文。另外,还有其他几种类型的报文:802.11 Action、802.11 BAR 和 802.11BA、802.11 Encrypted Data 密匙认证协议EAPOL: EAP是Extensible Authentication Protocol的缩写,EAPOL就是(EAP…...
C++类和对象
目录 一、C类定义 二、定义C对象 三、访问数据成员 四、类和对象详解 C 在 C 语言的基础上增加了面向对象编程,C 支持面向对象程序设计。类是 C 的核心特性,通常被称为用户定义的类型。 类用于指定对象的形式,它包含了数据表示法和用于处…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
