当前位置: 首页 > news >正文

62. 不同路径

62. 不同路径

一个机器人位于一个 m∗nm * nmn 网格的左上角 (起始点在下图中标记为 “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^92109

思路:(动态规划)

由于每次只能向下或者向右移动,所以到达任意一个位置,不是从上面到达就是从左边到达,从而到达该位置的路径就是这两个方向之和:

  • 定义一个 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 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xff09;。 问总共有多少条不同的路…...

在windows安装python3.11同时进行一个数据的练习

安装包百度网盘如下&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1l9H1GWP64LOxLaXXLie2uA?pwd6666 提取码&#xff1a;6666 1.我们选择自定义安装 2.当我们点了自定义安装后就直接next 3.修改路径&#xff0c;之后点击安装(install) 4.安装完成&#xff0c;进行…...

Java接口专题

基本介绍 接口给出一些没有实现的方法&#xff0c;封装到一起&#xff0c;到某个类使用时再根据具体情况把这些方法写出来。 注意&#xff1a;在jdk7之前&#xff0c;接口里所有的方法都是抽象方法。在jdk8之后接口中可以有静态方法&#xff0c;默认方法 interface 接口名{/…...

6招优化WordPress打开速度-让你的网站飞起来

为什么我们的WordPress网站比你的快&#xff1f; 我们的官网是使用WordPress框架搭建的&#xff0c;有没有发现我们的网站非常快&#xff0c;而你的WordPress网站比较慢呢&#xff1f;那是因为我们的网站经过了优化。 WordPress 很慢&#xff1f; 为什么很多人都会觉得 Word…...

春天到了,来一场 VoxEdit 创作大赛吧!

春天的气息扑面而来&#xff0c;这是让你尽情绽放创造力的最佳时机&#xff01;我们将以「春天」为主题来一场 VoxEdit 大赛。在这里&#xff0c;你可以展示你的才华并赢得 $SAND 奖励&#xff01; 无论你是专业的设计师&#xff0c;还是仅仅喜欢创造美丽的艺术&#xff0c;这场…...

异步Buck和同步Buck的特点

1 介绍 随着时代的发展&#xff0c;工业&#xff0c;车载&#xff0c;通信&#xff0c;消费类等产品都提出了小型化&#xff0c;智能化的需求。相应的&#xff0c;对于这些系统中的电源模块提出了小型化的要求。目前&#xff0c;市场上依然存在很多异步Buck电源管理芯片使用的场…...

基于轻量级YOLO开发构建中国象棋目标检测识别分析系统

关于棋类相关的项目在我之前的博文里面都有做过&#xff0c;如下&#xff1a;《yolov5s融合SPD-Conv用于提升小目标和低分辨率图像检测性能实践五子棋检测识别》《YOLOV5融合SE注意力机制和SwinTransformer模块开发实践的中国象棋检测识别分析系统》《基于yolov5s实践国际象棋目…...

机器学习100天(三十五):035 贝叶斯公式

《机器学习100天》完整目录:目录 机器学习100天,今天讲的是:贝叶斯公式! 好了,上一节介绍完先验概率、后验概率、联合概率、全概率后,我们来看这样一个问题:如果我现在挑到了一个瓜蒂脱落的瓜,则该瓜是好瓜的概率多大? 显然,这是一个计算后验概率的问题,根据我们之…...

大话数据结构-栈

1 概述 栈&#xff08;Stack&#xff09;是限定仅在表尾进行插入和删除操作的线性表。 允许插入和删除的一端称为栈顶&#xff08;top&#xff09;&#xff0c;另一端称为栈底&#xff08;bottom&#xff09;&#xff0c;不含任何数据元素的栈称为空栈&#xff0c;栈又称为后进…...

javaFx实现放大镜效果——圆形、矩形、三角形放大镜,拖动调整放大镜大小,设置放大倍数

系列文章专栏:javafx图形绘制、桌面录屏录音源码合集 目录 一、实现的效果 二、实现思路 三、程序实现...

什么是客户忠诚度?建立忠诚文化的 5 种方法

客户忠诚度影响企业的各个方面&#xff0c;例如收入、品牌形象、预算分配和产品路线图。拥有忠实的客户群对于建立成功的企业至关重要&#xff0c;因为您的客户是您的主要拥护者&#xff0c;有助于为您的企业营造积极的氛围。 什么是客户忠诚度&#xff1f; 客户忠诚度衡量客户…...

【ROS2知识】关于colcon编译和ament指定

一、说明 这里说说编译和包生成的操作要点&#xff0c;以python包为例。对于初学者来说&#xff0c;colcon和ament需要概念上搞清楚&#xff0c;与此同时&#xff0c;工作空间、包、节点在一个工程中需要熟练掌握。本文以humble版的ROS2&#xff0c;进行python编程的实现。 二、…...

数据结构: 最小栈

最小栈的特色是保持栈后进先出的特性&#xff0c;同时能够以O(1)复杂度获得当前栈的最小值。 栈是比较好实现的&#xff0c;直接搞个链表&#xff0c;从头部删除和添加即可。 最小栈的核心逻辑是&#xff1a; 因为栈是后进先出的&#xff0c;因此栈顶元素之下的数字永远在栈…...

STM32之PWM

PWMPWM&#xff0c;英文名Pulse Width Modulation&#xff0c;是脉冲宽度调制缩写&#xff0c;它是通过对一系列脉冲的宽度进行调制&#xff0c;等效出所需要的波形&#xff08;包含形状以及幅值&#xff09;&#xff0c;对模拟信号电平进行数字编码&#xff0c;也就是说通过调…...

操作系统(1.1)--引论

目录 一、操作系统的目标和作用 1.操作系统的目标 2.操作系统的作用 2.1 OS作为用户与计算机硬件系统之间的接口 2.2 OS作为计算机系统资源的管理者 2.3 0S实现了对计算机资源的抽象 3. 推动操作系统发展的主要动力 二、操作系统的发展过程 1.无操作系统的计算机系统…...

Spring boot + mybatis-plus 遇到 数据库字段 创建不规范 大驼峰 下划线 导致前端传参数 后端收不到参数 解决方案

最近使用springboot 连接了一个 sqlserver 数据库 由于数据库年数久远 &#xff0c;建表字段不规范 大驼峰 下划线的字段名都有 但是 java 中 Spring boot mybatis-plus 又严格按照小驼峰 格式 生成实体类 如果不是小驼峰格式 Data 注解 get set 方法 在前端请求参数 使用这个…...

JavaScript String 字符串对象

文章目录JavaScript String 字符串对象JavaScript 字符串字符串&#xff08;String&#xff09;在字符串中查找字符串内容匹配替换内容字符串大小写转换字符串转为数组特殊字符字符串属性和方法JavaScript String 字符串对象 String 对象用于处理已有的字符块。 JavaScript 字…...

Lazada如何做好店铺运营?产品定价是关键

1.东南亚各国状况一览&#xff08;对比中国&#xff09; 2.东南亚消费水平真的很低&#xff1f; 精准定价的意义&#xff1a;定价过高&#xff0c;失去核心竞争力&#xff1b;定价过低&#xff0c;亏本对市场失去信心&#xff1b;价格改动&#xff0c;流量下降 定价公式&#…...

空口协议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 语言的基础上增加了面向对象编程&#xff0c;C 支持面向对象程序设计。类是 C 的核心特性&#xff0c;通常被称为用户定义的类型。 类用于指定对象的形式&#xff0c;它包含了数据表示法和用于处…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...