当前位置: 首页 > 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;它包含了数据表示法和用于处…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...