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

leetcode做题笔记62

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

思路一:动态规划

int uniquePaths(int m, int n){int dp[m][n];int i,j=0;for(i=0;i<m;++i){for(j=0;j<n;++j){if(i==0||j==0){dp[i][j]=1;}else{dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[m-1][n-1];
}

时间复杂度O(mn),空间复杂度O(mn)

分析:

本题要求从左上角到右下角共有多少条不同路径,可利用动态规划,到每个格子的不同路径等于到左边前一个路径数加上边前一个路径数,最后返回dp[m-1][n-1]

思路二:组合排列

int Combinations(int up, int down){long prod = 1;int left = down - up + 1, right = 1;while(right <= up){prod *= left;prod /= right;left++;right++;}return prod;
}int uniquePaths(int m, int n){int para = (m - 1 < n - 1) ? m - 1 : n - 1;return Combinations(para, m + n - 2);
}

时间复杂度O(n),空间复杂度O(1)

分析:

本题同时可直接用排列组合进行计算,因为机器人需要向下走n-1步,向右走m-1步,即共走m+n-2步中间有n-1步向下走,计算即可得到答案。

比较:

两个思路比较,组合排列的方式可直接计算结果,避免构造数组,在内存方面占优,且组合排列计算的时间复杂度为O(n)优于第一种不断向后递推的思路,运行速度更快。

总结:

本题考察动态规划的应用,每个格子考虑左边前一个和上边前一个的值,或直接使用组合排列的方法得到答案。

相关文章:

leetcode做题笔记62

一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xff09;。 问总共有多少条不同的路径&#xff1f; 思路一…...

图论 <最短路问题>模板

图论 <最短路问题> 有向图 1.邻接矩阵&#xff0c;稠密图 2.邻接表 &#xff08;常用&#xff09;单链表&#xff0c;每一个点都有一个单链表 &#xff0c;插入一般在头的地方插&#xff0c; 图的邻接表的存储方式 树的深度优先遍历 特殊的深度优先搜索&#xff0c…...

计算机网络性能指标

比特&#xff1a;数据量的单位 KB 2^10B 2^13 bit 比特率&#xff1a;连接在计算机网络上的主机在数字通道上传送比特的速率 kb/s 10^3b/s 带宽&#xff1a;信号所包含的各种频率不同的成分所占据的频率范围 Hz 表示在网络中的通信线路所能传送数据的能力&#xff08…...

vue + elementUI 实现下拉树形结构选择部门,支持多选,支持检索

vue elementUI 实现下拉树形结构选择部门&#xff0c;支持多选&#xff0c;支持检索 <template><div><el-select v-model"multiple?choosedValue:choosedValue[0]" element-loading-background"rgba(0,0,0,0.8)":disabled"disableFl…...

招投标系统简介 企业电子招投标采购系统源码之电子招投标系统 —降低企业采购成本 tbms

​功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外…...

半监督学习(主要伪标签方法)

半监督学习 1. 引言 应用场景&#xff1a;存在少量的有标签样本和大量的无标签样本的场景。在此应用场景下&#xff0c;通常标注数据是匮乏的&#xff0c;成本高的&#xff0c;难以获取的&#xff0c;与之相对应的是却存在大量的无标注数据。半监督学习的假设&#xff1a;决策…...

datePicker一个或多个日期组件,如何快捷选择多个日期(时间段)

elementUI的组件文档中没有详细说明type"dates"如何快捷选择一个时间段的日期&#xff0c;我们可以通过picker-options参数来设置快捷选择&#xff1a; <div class"block"><span class"demonstration">多个日期</span><el…...

【语音合成】微软 edge-tts

目录 1. edge-tts 介绍 2. 代码示例 1. edge-tts 介绍 https://github.com/rany2/edge-tts 在Python代码中使用Microsoft Edge的在线文本到语音服务 2. 代码示例 import asyncio # pip install edge_tts import edge_tts TEXT """给我放首我喜欢听的歌曲…...

elevation mapping学习笔记3之使用D435i相机离线或在线订阅点云和tf关系生成高程图

文章目录 0 引言1 数据1.1 D435i相机配置1.2 协方差位姿1.3 tf 关系2 离线demo2.1 yaml配置文件2.2 launch启动文件2.3 数据录制2.4 离线加载点云生成高程图3 在线demo3.1 launch启动文件3.2 CMakeLists.txt3.3 在线加载点云生成高程图0 引言 elevation mapping学习笔记1已经成…...

ESP32 Max30102 (3)修复心率误差

1. 运行效果 2. 新建修复心率误差.py 代码如下: from machine import sleep, SoftI2C, Pin, Timer from utime import ticks_diff, ticks_us from max30102 import MAX30102, MAX30105_PULSE_AMP_MEDIUM from hrcalc import calc_hr_and_spo2BEATS = 0 # 存储心率 FINGER_F…...

16-4_Qt 5.9 C++开发指南_Qt 应用程序的发布

文章目录 1. 应用程序发布方式2. Windows 平台上的应用程序发布 1. 应用程序发布方式 用 Qt 开发一个应用程序后&#xff0c;将应用程序提供给用户在其他计算机上使用就是应用程序的发布。应用程序发布一般会提供一个安装程序&#xff0c;将应用程序的可执行文件及需要的运行库…...

oracle容灾备份怎么样Oracle容灾备份

随着科学技术的发展和业务的增长&#xff0c;数据安全问题越来越突出。为了保证数据的完整性、易用性和保密性&#xff0c;公司需要采取一系列措施来防止内容丢失的风险。  Oracle是一个关系数据库管理系统(RDBMS),OracleCorporation是由美国软件公司开发和维护的。该系统功能…...

AcWing 4957:飞机降落

【题目来源】https://www.acwing.com/problem/content/4960/【题目描述】 有 N 架飞机准备降落到某个只有一条跑道的机场。 其中第 i 架飞机在 Ti 时刻到达机场上空&#xff0c;到达时它的剩余油料还可以继续盘旋 Di 个单位时间&#xff0c;即它最早可以于 Ti 时刻开始降落&…...

强化学习研究 PG

由于一些原因&#xff0c; 需要学习一下强化学习。用这篇博客来学习吧&#xff0c; 用的资料是李宏毅老师的强化学习课程。 深度强化学习(DRL)-李宏毅1-8课&#xff08;全&#xff09;_哔哩哔哩_bilibili 这篇文章的目的是看懂公式&#xff0c; 毕竟这是我的弱中弱。 强化…...

uniapp微信小程序 401时重复弹出登录弹框问题

APP.vue 登陆成功后&#xff0c;保存登陆信息 if (res.code 200) {uni.setStorageSync(loginResult, res)uni.setStorageSync(token, res.token);uni.setStorageSync(login,false);uni.navigateTo({url: "/pages/learning/learning"}) }退出登录 toLogout: func…...

Cloud Studio实战——热门视频Top100爬虫应用开发

最近Cloud Studio非常火&#xff0c;我也去试了一下&#xff0c;感觉真的非常方便&#xff01;我就以Python爬取B站各区排名前一百的视频&#xff0c;并作可视化来给大家分享一下Cloud Studio&#xff01;应用链接&#xff1a;Cloud Studio实战——B站热门视频Top100爬虫应用开…...

php 去除二维数组重复

在 PHP 中&#xff0c;我们常常需要对数组进行处理和操作。有时候&#xff0c;我们需要去除数组中的重复元素&#xff0c;这里介绍一种针对二维数组的去重方法。 以下是列举一些常见的方法&#xff1a; 方法一&#xff1a;使用 array_map 和 serialize 函数 array_map 函数可以…...

玩转graphQL

转载至酒仙桥的玩转graphQL - SecPulse.COM | 安全脉搏 前言 在测试中我发现了很多网站开始使用GraphQL技术&#xff0c;并且在测试中发现了其使用过程中存在的问题&#xff0c;那么&#xff0c;到底GraphQL是什么呢&#xff1f;了解了GraphQL后能帮助我们在渗透测试中发现哪些…...

神经网络super(XXX, self).__init__()的含义

学习龙良曲老师的课程&#xff0c;在77节有这样一段代码 import torch from torch import nnclass Lenet5(nn.Module):def __init__(self):super(Lenet5,self).__init__()那么&#xff0c;super(XXX, self).init()的含义是什么&#xff1f; Python中的super(Net, self).init()…...

45.杜芬方程解仿真解曲线(matlab程序)

1.简述 Dufing方程是一种重要的动力系统山&#xff0c;是反映工程物理系统中非线性现象和混沌动力学行为的极其重要的方程式。通过Duffing方程可以探讨铁磁谐振电路中的分岔、拟周期运动、子谐波振荡。而在非线性与混沌系统的研究中&#xff0c;Duffing方程展示了丰富的混沌动力…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...