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

每日OJ题_记忆化搜索②_力扣62. 不同路径(三种解法)

目录

力扣62. 不同路径

解析代码1_暴搜递归(超时)

解析代码2_记忆化搜索

解析代码3_动态规划


力扣62. 不同路径

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 * 10^9
class Solution {
public:int uniquePaths(int m, int n) {}
};

解析代码1_暴搜递归(超时)

  • 递归含义:给 dfs 一个下标,返回从 [0, 0] 位置走到 [i, j] 位置一共有多少种方法。
  • 函数体:只要知道到达上面位置的方法数以及到达左边位置的方法数,然后累加起来即可。
  • 递归出口:当下标越界的时候返回 0 ,当位于起点的时候,返回 1 。
class Solution {
public:int uniquePaths(int m, int n) {return dfs(m, n);}int dfs(int sr, int sc){if(sr == 0 || sc == 0)return 0;if(sr == 1 && sc == 1)return 1;return dfs(sr - 1, sc) + dfs(sr, sc - 1);}
};


解析代码2_记忆化搜索

记忆化搜索解法:

  • 加上一个备忘录。
  • 每次进入递归的时候,去备忘录里面看看。
  • 每次返回的时候,将结果加入到备忘录里面。
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> memo(m + 1, vector<int>(n + 1));return dfs(m, n, memo);}int dfs(int sr, int sc, vector<vector<int>>& memo){if(sr == 0 || sc == 0)return 0;if(sr == 1 && sc == 1)return 1;if(memo[sr][sc] != 0)return memo[sr][sc];memo[sr][sc] = dfs(sr - 1, sc, memo) + dfs(sr, sc - 1, memo);return memo[sr][sc];}
};


解析代码3_动态规划

根据记忆化搜索得出动态规划的解法:

  • 递归含义:状态表示
  • 函数体:状态转移方程
  • 递归出口:初始化
  • 填表顺序:填备忘录的顺序
  • 返回值:备忘录的值
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));dp[1][1] = 1;for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){if(i == 1 && j == 1)continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];}
};

相关文章:

每日OJ题_记忆化搜索②_力扣62. 不同路径(三种解法)

目录 力扣62. 不同路径 解析代码1_暴搜递归&#xff08;超时&#xff09; 解析代码2_记忆化搜索 解析代码3_动态规划 力扣62. 不同路径 62. 不同路径 难度 中等 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器…...

【微信小程序开发】微信小程序、大前端之flex布局方式详细解析

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

代码随想录算法训练营第二十天:二叉树成长

代码随想录算法训练营第二十天&#xff1a;二叉树成长 110.平衡二叉树 力扣题目链接(opens new window) 给定一个二叉树&#xff0c;判断它是否是高度平衡的二叉树。 本题中&#xff0c;一棵高度平衡二叉树定义为&#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝…...

Opensbi初始化分析:设备初始化-warmboot

Opensbi初始化分析:设备初始化-warmboot 设备初始化sbi_init函数init_warmboot函数coolboot & warmbootwait_for_coldboot函数domain && scratch(coldboot所特有)console初始化及print相关工作(coldboot所特有)系统调用的相关初始化(coldboot所特有)综上设备…...

软考 系统架构设计师系列知识点之软件可靠性基础知识(13)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之软件可靠性基础知识&#xff08;12&#xff09; 所属章节&#xff1a; 第9章. 软件可靠性基础知识 第3节 软件可靠性管理 为了进一步提高软件可靠性&#xff0c;人们又提出了软件可靠性管理的概念&#xff0c;把软件可…...

将ESP工作为AP路由模式并当成服务器

将ESP8266模块通过usb转串口接入电脑 ATCWMODE3 //1.配置成双模ATCIPMUX1 //2.使能多链接ATCIPSERVER1 //3.建立TCPServerATCIPSEND0,4 //4.发送4个字节在链接0通道上 >ATCIPCLOSE0 //5.断开连接通过wifi找到安信可的wifi信号并连接 连接后查看自己的ip地址变为192.168.4.…...

Python深度学习基于Tensorflow(6)神经网络基础

文章目录 使用Tensorflow解决XOR问题激活函数正向传播和反向传播解决过拟合权重正则化Dropout正则化批量正则化 BatchNormal权重初始化残差连接 选择优化算法传统梯度更新算法动量算法NAG算法AdaGrad算法RMSProp算法Adam算法如何选择优化算法 使用tf.keras构建神经网络使用Sequ…...

力扣HOT100 - 35. 搜索插入位置

解题思路&#xff1a; 二分法模板 class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length - 1;while (left < right) {int mid left ((right - left) >> 1);if (nums[mid] target)return mid;else if (nums[mid…...

MinimogWP WordPress 主题下载——优雅至上,功能无限

无论你是个人博客写手、创意工作者还是企业站点的管理员&#xff0c;MinimogWP 都将成为你在 WordPress 平台上的理想之选。以其优雅、灵活和功能丰富而闻名&#xff0c;MinimogWP 不仅提供了令人惊叹的外观&#xff0c;还为你的网站带来了无限的创作和定制可能性。 无与伦比的…...

kube-prometheus部署到 k8s 集群

文章目录 **修改镜像地址****访问配置****修改 Prometheus 的 service****修改 Grafana 的 service****修改 Alertmanager 的 service****安装****Prometheus验证****Alertmanager验证****Grafana验证****卸载****Grafana显示时间问题** 或者配置ingress添加ingress访问grafana…...

从0开始学习python(六)

目录 前言 1、循环结构 1.1 遍历循环结构for 1.2 无限循环结构while 总结 前言 上一篇文章我们讲到了python的顺序结构和分支结构。这一章继续往下讲。 1、循环结构 在python中&#xff0c;循环结构分为两类&#xff0c;一类是遍历循环结构for&#xff0c;一类是无限循环结…...

OpenGL 入门(三)—— OpenGL 与 OpenCV 共同打造大眼滤镜

从本篇开始&#xff0c;会在上一篇搭建的滤镜框架的基础上&#xff0c;介绍具体的滤镜效果该如何制作。本篇会先介绍大眼滤镜&#xff0c;先来看一下效果&#xff0c;原图如下&#xff1a; 使用手机后置摄像头对眼部放大后的效果&#xff1a; 制作大眼滤镜所需的主要知识点&…...

Linux服务器安全基础 - 查看入侵痕迹

1. 常见系统日志 /var/log/cron 记录了系统定时任务相关的日志 /var/log/dmesg 记录了系统在开机时内核自检的信息&#xff0c;也可以使用dmesg命令直接查看内核自检信息 /var/log/secure:记录登录系统存取数据的文件;例如:pop3,ssh,telnet,ftp等都会记录在此. /var/log/btmp:记…...

Java反射机制的实战应用:探索其魅力与局限

引言 Java作为一种面向对象的编程语言&#xff0c;其灵活性和强大的功能使其成为众多开发者的首选。而Java反射机制作为Java语言中的一项重要特性&#xff0c;为程序员提供了一种在运行时检查和操作类、方法、属性等信息的能力。本文旨在深入探讨Java反射机制的实战应用&#…...

vue3项目 文件组成

从头捋顺一遍vue3项目文件目录 前置知识JS模块化什么是依赖&#xff1f;安装依赖webpack能做什么&#xff1f;vue基本使用 不借助vue-cli&#xff0c;从0开始搭建vue项目。index.html、main.js、App.vue引入npm引入webpack引入babel引入vue-loaderwebpack配置webpack配置 前置知…...

C语言关键字 typedef 的功能是什么?

一、问题 语⾔有 32 个关键字&#xff0c;其中 int 的功能是声明整型变量&#xff0c;struct 的功能是声明结构体变量&#xff0c;那么 typedef 的功能是什么呢&#xff1f; 二、解答 1. typedef 的功能 在 C 语⾔中除了可以使⽤标准类型名&#xff08;如 int、 char、float …...

【YoloDeployCsharp】基于.NET Framework的YOLO深度学习模型部署测试平台-源码下载与项目配置

基于.NET Framework 4.8 开发的深度学习模型部署测试平台,提供了YOLO框架的主流系列模型,包括YOLOv8~v9,以及其系列下的Det、Seg、Pose、Obb、Cls等应用场景,同时支持图像与视频检测。模型部署引擎使用的是OpenVINO™、TensorRT、ONNX runtime以及OpenCV DNN,支持CPU、IGP…...

如何在 Ubuntu 12.04 VPS 上使用 MongoDB 创建分片集群

简介 MongoDB 是一个 NoSQL 文档数据库系统&#xff0c;可以在水平方向上很好地扩展&#xff0c;并通过键值系统实现数据存储。作为 Web 应用程序和网站的热门选择&#xff0c;MongoDB 易于实现并可以通过编程方式访问。 MongoDB 通过一种称为“分片”的技术实现扩展。分片是将…...

阿里云VOD视频点播流程(1)

一、开通阿里云VOD 视频点播&#xff08;ApsaraVideo VoD&#xff0c;简称VOD&#xff09;是集视频采集、编辑、上传、媒体资源管理、自动化转码处理、视频审核分析、分发加速于一体的一站式音视频点播解决方案。登录阿里云&#xff0c;在产品找到视频点播VOD &#xff0c;点击…...

Python爬虫获取豆瓣电影Top100

大家好&#xff0c;我是秋意零。 今天分析一篇&#xff0c;Python爬虫获取豆瓣电影Top100。 在此之前&#xff0c;我没有学习过爬虫&#xff0c;只有一丢丢的Python基础。下面效果的实现源码几乎没经过我&#xff0c;而是AI百老师。我主要负责了对应的调试以及根据我想要的功…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

稳定币的深度剖析与展望

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

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...