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 的核心特性,通常被称为用户定义的类型。 类用于指定对象的形式,它包含了数据表示法和用于处…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
