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

代码随想录学习Day 34

62.不同路径

题目链接

讲解链接

动归五部曲:
1.确定dp数组及其下标的含义:dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数;

2.确定递推公式:因为只能往右或者往下,所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

3.dp数组初始化:初始化为m * n的全1数组。

4.确定遍历顺序:因为递推公式为dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

5.举例推导dp数组:m = 3,n = 7时,dp = [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[1] * n for _ in range(m)]  # 初始化为全1数组,因为第一列和第一行一定都是1for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1]  # 递推公式return dp[-1][-1]

63.不同路径Ⅱ 

题目链接

讲解链接

本题大体思路同上,只需要对障碍物处额外处理一下。

在初始化时,如果第一列或第一行有障碍物,则将该位置的dp至设为0;在后续遍历过程中若遇到障碍物,则同样将该位置设为0,之后按照与上一题同样的方法计算即可。

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:i, j = 0, 0m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]while i < m and obstacleGrid[i][0] == 0:  # 初始化列,第一列除了障碍物处均为1dp[i][0] = 1i += 1while j < n and obstacleGrid[0][j] == 0:  #  同上,第一行除障碍均为1dp[0][j] = 1j += 1for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] == 1:  # 若遇到障碍处则将该位置的dp置为0dp[i][j] = 0else:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]  # 递推公式return dp[-1][-1]

相关文章:

代码随想录学习Day 34

62.不同路径 题目链接 讲解链接 动归五部曲&#xff1a; 1.确定dp数组及其下标的含义&#xff1a;dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数&#xff1b; 2.确定递推公式&#xff1a;因为只能往右或者往下&#xff0c;所以dp[i][j] dp[i - 1][j] dp[i][j - 1]。 3.…...

由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题

由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题 一、问题详细描述二、问题产生背景三、问题原因四、解决办法1、安装缺少的库2、直接更换更高版本的opencv 五、vs版本对应vc1、版本对应2、vs对应vc查看方法 一、问题详细描述 同样可能会报 &#xff…...

【前端】输入时字符跳动动画实现

输入时字符跳动动画实现 在前端开发中&#xff0c;为了提升用户体验&#xff0c;我们经常需要为用户的交互行为提供即时的反馈。这不仅让用户知道他们的操作有了响应&#xff0c;还可以让整个界面看起来更加生动、有趣。本文将通过一个简单的例子讲解如何实现在用户输入字符时…...

C语言面试重点问题

1. 冒泡排序法 2. strlen、strcpy、strcat、strcmp的用法和原理 3. 大小端的区分 3.1 主函数区分大小端 #include <stdio.h>int main(void) {int num 0x11223344;char *p (char *)&num;if (0x11 *p){printf("大端!\n");}else if (0x44 *p){printf(…...

antlr4略解

文章目录 1. antlr4是用来干什么的&#xff1f;2. 什么是lexer和parser&#xff1f;3. 使用antlr4生成某语言的lexer和parser的具体过程4. 其他 1. antlr4是用来干什么的&#xff1f; 是用来生成某语言lexer和parser的。 通俗点说&#xff0c;就是输入一个语言的规则描述文件&…...

超级好用的C++实用库之文件目录操作

&#x1f4a1; 需要该C实用库源码的大佬们&#xff0c;可扫码关注文章末尾的微信公众号二维码&#xff0c;或搜索微信公众号“希望睿智”。添加关注后&#xff0c;输入消息“超级好用的C实用库”&#xff0c;即可获得源码的下载链接。 概述 文件和目录操作是操作系统层面上的基…...

结合kimi chat的爬虫实战思路

背景 想钻研一下项目组件&#xff0c;找找之后的学习方向。不能自以为是&#xff0c;所以借着网开源项目网站上公布的项目内容看一下&#xff0c;那些是我可以努力去学习的&#xff08;入门的&#xff09;。首先需要获取相关内容&#xff0c;于是爬取整理。 任务1&#xff1a…...

UnsupportedClassVersionError异常如何解决?

下面是异常报错的详细描述 java -version java version "17.0.11" 2024-04-16 LTS Java(TM) SE Runtime Environment (build 17.0.117-LTS-207) Java HotSpot(TM) 64-Bit Server VM (build 17.0.117-LTS-207, mixed mode, sharing) 环境变量已经是jdk17&#xff0c;但…...

LeetCode热题100|动态规划Part.1|70.爬楼梯、118.杨辉三角、198.打家劫舍

70.爬楼梯 代码随想录原题&#xff0c;看这篇文章&#xff1a;C动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯 118.杨辉三角 题目链接&#xff1a;118.杨辉三角 一刷代码 时间复杂度和空间复杂度都造到 O ( n u m R o w s 2 ) O(num…...

python 根据网址和关键词批量下载影像

最近用到了GLASS的LAI产品&#xff0c;但这个产品的文件夹分得很细&#xff0c;我需要的影像又有8个瓦片&#xff0c;一个一个点击很麻烦&#xff0c;于是探索了批量下载的方法 一、下载1幅 import requests import re import os import requests import re# 网页URLurl &…...

爬虫-无限debug场景 解决方式

解决无限debug 场景1 1. 鼠标右键 选择 continue to here&#xff08;此处不停留&#xff09;2. 鼠标右键 选择 edite breakpoint 设置 10 保证条件不成立 这行永远不执行3.方法置空 1. 方法调用加断点2. 控制台 setInterval function name() {}4. 替换文件 5. hoo…...

[链表专题]力扣206, 203, 19

1. 力扣206 : 反转链表 (1). 题 : 图略 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。示例 1&#xff1a;输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a;输入&#xff1a;head [1,2] 输出&#x…...

秋招后端开发面试题 - MySQL基础

目录 MySQL基础前言面试题MySQL 基础篇Mysql 的基础架构&#xff1f;MySQL 的长连接和短连接长连接引起的异常重启问题&#xff1f;说一下 MySQL 执行一条查询语句的内部执行过程&#xff1f;MySQL 查询缓存的功能有何优缺点&#xff1f;MySQL 的常用引擎都有哪些&#xff1f;I…...

力扣每日一题113:路径总和||

题目 中等 给你二叉树的根节点 root 和一个整数目标和 targetSum &#xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSu…...

Thinkphp5 中常见的session 操作方法

在 ThinkPHP 框架中&#xff0c;session 是用于在多个页面或请求之间存储用户信息的机制。以下是在 ThinkPHP 中进行 session 常见操作的一些示例&#xff1a; 启动 Session 在 ThinkPHP 中&#xff0c;通常不需要手动启动 Session&#xff0c;因为框架会在应用启动时自动处理…...

inBuilder 低代码平台新特性推荐 - 第十八期

今天来给大家带来的是inBuilder低代码平台特性推荐系列第十八期——表单设计器集成预约日历组件。 一、场景介绍 项目上希望用日历的形式展示某地点在一段时间内的预约记录&#xff0c;表单设计器新增支持创建日历预约视图&#xff0c;并配置预约属性。 二、运行效果 三、前…...

部署xwiki服务需要配置 hibernate.cfg.xml如何配置?

1. 定位 hibernate.cfg.xml 文件 首先&#xff0c;确保您可以在 Tomcat 的 XWiki 部署目录中找到 hibernate.cfg.xml 文件&#xff1a; cd /opt/tomcat/latest/webapps/xwiki/WEB-INF ls -l hibernate.cfg.xml如果文件存在&#xff0c;您可以继续编辑它。如果不存在&#xff…...

1376:信使(msner)

【解题思路】 每个哨所是一个顶点&#xff0c;哨所与哨所之间的通信线路为边&#xff0c;两哨所间通讯花费的时间为边的权值。记第一个哨所为顶点s&#xff0c;信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径&#xff0c;每条传送路径有一个花费的时间&…...

Hadoop3:HDFS的架构组成

一、官方文档 我这里学习的是Hadoop3.1.3版本&#xff0c;所以&#xff0c;查看的也是3.1.3版本的文档 Architecture模块最下面 二、HDFS架构介绍 HDFS架构的主要组成部分&#xff0c;是一下四个部分 1、NameNode(NN) 就是Master节点&#xff0c;它是集群管理者。 1、管…...

P2910 [USACO08OPEN] Clear And Present Danger S

Problem: P2910 [USACO08OPEN] Clear And Present Danger S 文章目录 思路解题方法复杂度Code 思路 这是一个图论问题&#xff0c;我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先&#xff0c;我们需要构建一个距离矩阵&am…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法

目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客&#xff1a;【写在创作纪念日】基于SpringBoot和PostG…...