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

力扣62.不同路径

文章目录

  • 力扣62.不同路径
    • 题目描述
    • 方法1:暴力深搜(超时未通过)
    • 方法2:动态规划

力扣62.不同路径

题目描述

一个机器人位于一个 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 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

方法1:暴力深搜(超时未通过)

使用最经典的深搜dfs模板搜索全部路线,每搜索到一个路线让全局变量count++,最终返回count,但由于其指数级的时间复杂度最终导致结果超时

int count=0;
void dfs(int m,int n,int **book,int i,int j)
{if(i==m-1&&j==n-1){count++;return;}if(i+1<m&&j<n&&book[i+1][j]==0){book[i+1][j]=1;dfs(m,n,book,i+1,j);book[i+1][j]=0;}if(i<m&&j+1<n&&book[i][j+1]==0){book[i][j+1]=1;dfs(m,n,book,i,j+1);book[i][j+1]=0;} 
}
int uniquePaths(int m, int n){
int **book=(int **)malloc(sizeof(int *)*m),i=0;
for(i=0;i<m;i++) book[i]=(int *)calloc(sizeof(int),n);
book[0][0]=1;
count=0;
dfs(m,n,book,0,0);
return count;
}

在这里插入图片描述

方法2:动态规划

思路:对于一个位置(i,j)的到达路线数,等于其正上方位置:(i-1,j)路线数加上其左边位置:(i,j-1)路线数之和。
即有状态转移方程:
dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]=dp[i1][j]+dp[i][j1]
开辟额外的O(mn)空间来存储每一位置的到达路线数
算法时间复杂度O(mn) 空间复杂度O(mn)

int uniquePaths(int m, int n){int results[m][n],i,j;for(i=0;i<m;i++) memset(results[i],0,sizeof(int)*n);results[0][0]=1;for(i=0;i<m;i++){for(j=0;j<n;j++){if(i-1>=0) results[i][j]+=(results[i-1][j]);if(j-1>=0) results[i][j]+=(results[i][j-1]);}}return results[m-1][n-1];
}

在这里插入图片描述

相关文章:

力扣62.不同路径

文章目录力扣62.不同路径题目描述方法1&#xff1a;暴力深搜(超时未通过)方法2&#xff1a;动态规划力扣62.不同路径 题目描述 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器…...

【验证码的识别】—— 图形验证码的识别

前言 &#xff08;结尾有彩蛋欧&#xff09; 目前&#xff0c;许多网站采取各种各样的措施来反爬虫&#xff0c;其中一个措施便是使用验证码。随着技术的发展&#xff0c;验证码的花样越来越多。验证码最初是几个数字组合的简单的图形验证码&#xff0c;后来加入了英文字母和混…...

RocketMQ云服务器和本地基础安装搭建及可视化控制台安装使用

一起学编程&#xff0c;让生活更随和&#xff01; 如果你觉得是个同道中人&#xff0c;欢迎关注博主gzh&#xff1a;【随和的皮蛋桑】。 专注于Java基础、进阶、面试以及计算机基础知识分享&#x1f433;。偶尔认知思考、日常水文&#x1f40c;。 目录一、RocketMQ 介绍1、Ro…...

JavaScript:简单理解防抖和节流,如何定义防抖和节流函数?

防抖 防抖函数&#xff0c;就是防止抖动&#xff0c;避免事件重复触发。比如监听输入框的输入&#xff0c;不应该在用户每输入一个字符就触发监听&#xff0c;而是在用户输入结束后再来监听。 流程为&#xff1a; 1、事件触发&#xff1b; 2、开启定时器&#xff1b; 3、当事…...

【opencv 系列】第3章 图像的8种变换

文章目录前言上代码1.1 复习读取和显示1.2 图像放大、缩小 cv2.resize()1.3 图像平移1.4 图像旋转1.5 图像仿射变换1.6 图像的裁剪1.7 位运算(AND, OR, XOR)1.8 图像的分离和融合1.9 颜色空间 color space前言 坦白说&#xff0c;这一章我认为是整个opencv系列最难的一张&…...

【C语言刷题】倒置字符串

解题思路与过程&#x1f4fd;️解题思路&#x1f4fd;️解题过程&#x1f527;1.输入&#x1f527;2.设计逆序函数&#x1f527;3.逆序整个字符串&#x1f527;4.逆序每个单词&#x1f4fd;️源码&#x1f4f7;先来看题&#x1f447;&#x1f4fd;️解题思路 &#x1f534; 首先…...

用switch语句编程设计一个简单的计算器程序,要求根据用户从键盘输入的表达式:

用switch语句编程设计一个简单的计算器程序&#xff0c;要求根据用户从键盘输入的表达式&#xff1a;操作数1 运算符op 操作数2计算表达式的值&#xff0c;指定的算术运算符为加&#xff08;&#xff09;、减&#xff08;-&#xff09;、乘&#xff08;*&#xff09;、除&#…...

uboot编译分析

uboot编译分析 V 1 –> Q ,在一行命令前面加上表示不会在终端输出命令 KCONFIG_CONFIG ? .config.config 默认是没有的&#xff0c;默认是需要使用命令“make xxx_defconofig”先对uboot进行配置&#xff0c;配置完成就会在uboot根目录下生成.config。如果后续自行调整…...

SpringCloud Alibaba集成Dubbo实现远程服务间调用

SpringCloud Alibaba集成Dubbo实现远程服务间调用 工程创建 一、创建springBoot分模块项目&#xff0c;父工程&#xff1a;springcloud-alibaba以及子模块product-dubbo-provider、order-dubbo-consumer等 项目基本结构图如下所示&#xff1a; 二、依赖引入 在以上两个子模块…...

网络编程(一)

网络编程 文章目录网络编程前置概念1- 字节序高低地址与高低字节高低地址&#xff1a;高低字节字节序大端小端例子代码判断当前机器是大端还是小端为何要有字节序字节序转换函数需要字节序转换的时机例子一例子二2- IP地址转换函数早期(不用管)举例现在与字节序转换函数相比:**…...

PVE硬件直通之强制IOMMU分组

文章目录检查是否直接支持IOMMU分组配置IOMMU分组不直接支持的需要更新内核参考检查是否直接支持IOMMU分组 下面 以SATA控制器为例&#xff0c;看pci设备是否可以直接支持IOMMU分组 /* 打印pci设备详细信息*/ lspci -vv /* 找到SATA controller 段落*/ 16:00.1 SATA controll…...

深入讲解Kubernetes架构-node

Kubernetes 通过将容器放入在节点&#xff08;Node&#xff09;上运行的 Pod 中来执行你的工作负载。 节点可以是一个虚拟机或者物理机器&#xff0c;取决于所在的集群配置。 每个节点包含运行 Pod 所需的服务&#xff1b; 这些节点由控制面负责管理。通常集群中会有若干个节点…...

XSS-labs-master

XSS 经典14关这边先说一下常用的弹窗手法<script>alert(1)</script> <script>confirm(1)</script> <script>alert(1)</script> <script>alert(/1/zyl)</script> <script>alert(document.cookie)</script> <scr…...

「可信计算」助力TLS 传输更安全

序言背景&#xff08;Satuation&#xff09;&#xff1a;TLS 是 TCP/IP 上的传输层安全协议&#xff0c;保护着数以亿万级的数据安全&#xff0c;我们在浏览器中输入的 https&#xff0c;就是受到 TLS 保护的。冲突&#xff08;complication&#xff09;&#xff1a;从可信计算…...

链表学习基础

链表 通过指针串联在一起的线性结构&#xff0c;每个节点由数据域和指针域两部分组成。链表节点在内存中的存储通常不是连续的&#xff0c;各节点通过指针连接在一起&#xff0c;其内存分布大致如下图所示。 定义 单链表 struct ListNode {// DATATYPE 可以是任意存放数据的…...

springboot整合阿里云oss文件服务器

springboot整合阿里云oss文件服务器一、申请Bucket二、 获取AccessKey ID、AccessKey Secret三、 springboot整合3.1 在application.yml 配置参数3.2 oss需要的pom3.3 配置 oss配置类3.4 oss的controller类3.5 oss的service类以及impl一、申请Bucket 进入该网址对象存储oss述 …...

数据分析:旅游景点销售门票和消费情况分析

数据分析&#xff1a;旅游景点销售门票和消费情况分析 文章目录数据分析&#xff1a;旅游景点销售门票和消费情况分析一、前言二、数据准备三、分析数据四、用户购买门票数量分析五、用户复购分析六、用户回购分析七、占比分析1.每个月分层用户占比情况。2.每月不同用户的占比3…...

Android问题解决方案(一):Android 打空包后提示没有”android:exported“的属性设置

Android 打空包后提示没有”android:exported“的属性设置Android 打空包后提示没有”android:exported“的属性设置1、问题&#xff1a;2、文档3、参考链接&#xff1a;4、解决方案&#xff1a;Android 打空包后提示没有”android:exported“的属性设置 1、问题&#xff1a; …...

Portraiture2023最新版人像图像后期处理软件

2023全新发布Portraiture 4是专注于图像后期处理软件研发的 Imagenomic, LLC产品之一&#xff0c;在摄影爱好者中有点影响力。Portraiture可以将繁琐复杂的人像磨皮操作极致简化&#xff0c;不论是普通爱好者或专业后期处理人员&#xff0c;均能一键完成。凭借优秀的AI算法和多…...

链表OJ(七)删除有序链表中重复的元素-I -II

目录 删除有序链表中重复的元素-I 删除有序链表中重复的元素-II 删除有序链表中重复的元素-I 描述 删除给出链表中的重复元素&#xff08;链表中元素从小到大有序&#xff09;&#xff0c;使链表中的所有元素都只出现一次 例如&#xff1a; 给出的链表为1→1→21→1→2,返回1…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...