当前位置: 首页 > 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方程展示了丰富的混沌动力…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...