代码随想录算法训练营第39天 | 62.不同路径, 63不同路径II
Leetcode - 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
笔记:
dp[i][j]的含义:到达二维图的(i,j)点的路径条数。
初始化:求的是到达重点的路径条数,所以我们到达(0,0)点的路径数量为1;
状态转移方程:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]因为只能向下或者向右走。
遍历顺序:就从小到大即可
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));dp[0][0] = 1;for(int i = 0; i < m; i++){dp[i][0] = 1;}for(int i = 0; i < n; i++){dp[0][i] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};
Leetcode - 63:不同路径
题目:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2:

输入:obstacleGrid = [[0,1],[0,0]] 输出:1
笔记:
加了点障碍我们就对其进行特殊处理,但不要忘记我们每次只能向右下方走,不会拐弯抹角的走。
dp[i][j]的含义:就是到达(i, j)点的路径数量;
初始化:我们需要对[i][0]和[0][i]这两条边进行初始化。遇到障碍物就直接break因为不可能有路径到后面的路了。
状态转移方程:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]但这里我们需要注意的是遇到障碍物我们要continue,肯定不能用break啊,因为我们又不知一种走的方法,也不想最外围那两条边只要路被堵了后面就坑定过不去了。
遍历顺序:从小到大;
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));for(int i = 0; i < m; i++){if(obstacleGrid[i][0] == 1){dp[i][0] = 0;break;}dp[i][0] = 1;}for(int i = 0; i < n; i++){if(obstacleGrid[0][i] == 1){dp[0][i] = 0;break;}dp[0][i] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(obstacleGrid[i][j] == 1){continue;}if(obstacleGrid[i][j] == 0){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
};
相关文章:
代码随想录算法训练营第39天 | 62.不同路径, 63不同路径II
Leetcode - 62:不同路径 题目: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” &#…...
Redis 的慢日志
Redis 的慢日志 Redis 的慢日志(Slow Log)是用于记录执行时间超过预设阈值的命令请求的系统。慢日志可以帮助运维人员和开发人员识别潜在的性能瓶颈,定位那些可能导致 Redis 性能下降或响应延迟的慢查询。以下是 Redis 慢日志的相关细节&…...
第十四届蓝桥杯第十题:蜗牛分享
问题描述 输入格式 输出格式 输出共一行,一个浮点数表示答案(四舍五入保留两位小数)。 样例输入 3 1 10 11 1 1 2 1样例输出 4.20样例说明 蜗牛路线:(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)(0,0)→(1,0)→(1,1)→(10,1…...
不懂技术的老板,如何避免过度依赖核心技术人员
在这个日新月异、技术驱动的时代,即使作为非技术背景的老板,也深知核心技术人员的价值。然而,过度依赖某几位核心技术人员,不仅可能带来经营风险,还可能限制企业的创新与发展。那么,不懂技术的老板…...
Vue系列-el挂载
<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>el:挂载点</title> </head> <body&g…...
python--os和os.path模块
>>> import os >>> #curdir #获取当前脚本的绝对路径 >>> os.curdir . >>> import os.path >>> #获取绝对路径 >>> os.path.abspath(os.curdir) C:\\Users\\GUOGUO>>> #chdir #修改当前目录 >&g…...
前端通用命名规范和Vue项目命名规范
通用命名规范 变量和常量命名:变量和常量的命名应具有描述性,清晰明了,使用驼峰命名法或下划线命名法,例如:firstName、MAX_VALUE。 函数和方法命名:函数和方法的命名应该能够准确描述其功能&…...
NTP服务搭建
一、ntpd和ntpdate区别 1.ntpd是自动执行的远程更新本地系统时钟的服务,是平滑同步; 2.ntpdate是手工执行的服务,也就是一般用它执行一次本地时间更新,如果做成半自动,可以写入到crontab自动任务,从而变成…...
Linux离线安装mysql,node,forever
PS:本文是基于centos7实现的,要求系统能够查看ifconfig和unzip解压命令, 实现无网络可安装运行 首先现在百度网盘的离线文件包****安装Xftp 和 Xshell 把机房压缩包传到 home目录下****解压unzip 包名.zip 获取IP先获取到 linux 主机的ip ifconfig Xftp 连接输入IP,然后按照…...
WPF中获取TreeView以及ListView获取其本身滚动条进行滚动
实现自行调节scoll滚动的位置(可相应获取任何控件中的内部滚动条) TreeView:TreeViewAutomationPeer lvap new TreeViewAutomationPeer(treeView); var svap lvap.GetPattern(PatternInterface.Scroll) as ScrollViewerAutomationPeer; var scroll svap.Owner as ScrollVie…...
C语言: 指针讲解
为什么需要指针? (1)指针的使用使得不同区域的代码可以轻易的共享内存数据。当然你也可以通过数据的复制达到相同的效果,但是这样往往效率不太好,因为诸如结构体等大型数据,占用的字节数多,复制很消耗性能…...
C#使用Stopwatch类来实现计时功能
前言 在 C# 中,Stopwatch 类是用于测量经过的时间的工具类,提供了高精度的计时功能。Stopwatch 类位于 System.Diagnostics 命名空间中。通常情况下,使用 Stopwatch 的流程是创建一个 Stopwatch 对象,然后调用 Start 方法开始计时…...
ubuntu18.04安装qt
ubuntu18.04安装qt 1、下载文件 比如我下载的是5.13.0版本 下载链接 2、安装 wget https://download.qt.io/archive/qt/5.13/5.13.0/qt-opensource-linux-x64-5.13.0.runsudo chmod x qt-opensource-linux-x64-5.13.0.runsudo ./qt-opensource-linux-x64-5.13.0.run参考文…...
ElasticSearch、java的四大内置函数式接口、Stream流、parallelStream背后的技术、Optional类
第四周笔记 一、ElasticSearch 1.安装 apt-get install lrzsz adduser -m es 创建用户组: useradd *-m* xiaoming(用户名) *PS:追加参数-m* passwd xiaoming(用户名) passwd xiaoming 输入新的 UNIX 密码: 重新输入新的 UNIX 密码&…...
深入MNN:开源深度学习框架的介绍、安装与编译指南
引言 在人工智能的世界里,深度学习框架的选择对于研究和应用的进展至关重要。MNN,作为一个轻量级、高效率的深度学习框架,近年来受到了众多开发者和研究人员的青睐。它由阿里巴巴集团开源,专为移动端设备设计,支持跨平…...
[LeetCode][400]第 N 位数字
题目 400. 第 N 位数字 给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字。 示例 1: 输入:n 3 输出:3 示例 2: 输入:n 11 输出:…...
clickhouse 查询group 分组最大值的一行数据。
按照 sql_finger_md5 分组取query_time_ms 最大的一行数据。 使用any函数可以去匹配到的第一行数据,所以可以先让数据按照query_time_ms 排序,然后再使用group by 和any结合取第一行数据,就是最大值的那一行数据。 selectany (time) as time…...
Python装饰器与生成器:从原理到实践
一、引言 Python 是一种功能强大且易于学习的编程语言,其丰富的特性使得开发者能够高效地完成各种任务。在 Python 中,装饰器和生成器是两个非常重要的概念,它们能够极大地增强代码的可读性和可维护性。本文将详细介绍如何学习 Python 装饰器…...
python-函数引入模块面向对象编程创建类继承
远离复读机行为 def calculate_BMI(weight,height):BMI weight / height**2if BMI < 18.5:category "偏瘦"elif BMI < 25:category "正常"elif BMI < 30:category "偏胖"else:category "肥胖"print(f"您的BMI分类…...
Spring:面试八股
文章目录 参考Spring模块CoreContainerAOP 参考 JavaGuide Spring模块 CoreContainer Spring框架的核心模块,主要提供IoC依赖注入功能的支持。内含四个子模块: Core:基本的核心工具类。Beans:提供对bean的创建、配置、管理功能…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
