当前位置: 首页 > 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…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...