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

代码随想录day39 || 动态规划 || 不同路径

62.不同路径

● 力扣题目链接
● 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
● 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
● 问总共有多少条不同的路径?

思路

● dp数组初始化,第一行第一列是1,然后某个位置只能从上面或者左面过来
● 时间复杂度:O(m × n)
● 空间复杂度:O(m × n)

代码

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < n; i++) {dp[0][i] = 1;}for (int i = 0; i < m; i++) {dp[i][0] = 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];}
}

63. 不同路径 II

● 力扣题目链接
● 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
● 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
● 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

思路

● 在初始化和遍历的时候加上是否是障碍物的判断

代码

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;}for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {dp[0][i] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}
// 空间优化
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[] dp = new int[n];for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {dp[i] = 1;}for (int i = 1; i < m; i++) {for (int j = 0; j < n; j++) {if (obstacleGrid[i][j] == 1) dp[j] = 0;else if (j != 0) dp[j] += dp[j - 1];}}return dp[n - 1];}
}

相关文章:

代码随想录day39 || 动态规划 || 不同路径

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

电商平台API接口采集电商平台淘宝天猫京东拼多多数据获取产品详情信息,销量,价格,sku案例

淘宝SKU详情接口是指&#xff0c;获取指定商品的SKU&#xff08;Stock Keeping Unit&#xff0c;即库存量单位&#xff09;的详细信息。SKU是指提供不同的商品参数组合的一个机制&#xff0c;通过不同的SKU来标识商品的不同组合形式&#xff0c;如颜色、尺寸等。SKU详情接口可以…...

The ‘<‘ operator is reserved for future use. 错误解决

The < operator is reserved for future use. 错误解决 在 PowerShell 终端执行 python learnstock.py < ldata.txt 发生错误&#xff0c; The < operator is reserved for future use.解决方法&#xff0c; cmd /c python learnstock.py < ldata.txt完结&#x…...

vulnhub靶机Thoth-Tech

下载地址&#xff1a;https://download.vulnhub.com/thothtech/Thoth-Tech.ova 主机发现 arp-scan -l 目标&#xff1a;192.168.21.148 端口扫描 nmap --min-rate 10000 -p- 192.168.21.148 服务扫描 nmap -sV -sT -O -p21,22,80 192.168.21.148 漏洞扫描 nmap --scriptvu…...

不可思议,无密码登录所有网站!

hello&#xff0c;我是小索奇 居然可以免密码登录你的网站&#xff1f;听起来是不是很恐怖 确实如此&#xff0c;Cookie可以用于保持用户在网站上的登录状态&#xff0c;从而实现 免密码登录&#xff0c;学会了不要做坏事哈 这里仅做免密码登录的实操&#xff0c;就不介绍Cooki…...

深度学习编译器关键组件

1 高层中间代码 为了克服传统编译器中采用的IR限制DL模型中复杂计算的表达的局限性&#xff0c;现有的DL编译器利用高层IR&#xff08;称为图IR&#xff09;进行高效的代码优化设计。 1.1 图表示 基于DAG的IR&#xff1a;基于DAG的IR是编译器构建计算图的最传统方法之一&…...

【C++】string类模拟实现下篇(附完整源码)

目录 1. resize2. 流插入<<和流提取>>重载2.1 流插入<<重载2.2 流提取 << 3. 常见关系运算符重载4. 赋值重载4.1浅拷贝的默认赋值重载4.2 深拷贝赋值重载实现4.3 赋值重载现代写法 5. 写时拷贝(了解&#xff09;6.源码6.1 string.h6.2 test.cpp 1. res…...

Android高级开发-APK极致优化

九道工序 1. SVG(Scalable Vector Graphics)可缩放矢量图 使用矢量图代替位图可以减小 APK 的尺寸&#xff0c;因为可以针对不同屏幕密度调整同一文件的大小&#xff0c;而不会降低图像质量。 矢量图首次加载时可能消耗更多的 CPU 资源。之后&#xff0c;二者的内存使用率和…...

Rocketmq--消息驱动

1 MQ简介 1.1 什么是MQ MQ&#xff08;Message Queue&#xff09;是一种跨进程的通信机制&#xff0c;用于传递消息。通俗点说&#xff0c;就是一个先进先出的数据结构。 1.2 MQ的应用场景 1.2.1 异步解耦 最常见的一个场景是用户注册后&#xff0c;需要发送注册邮件和短信通…...

华为云云耀云服务器L实例评测|centos系统搭建git私服

搭建git私服 前言一、华为云云耀云服务器L实例租用二、华为云云耀云服务器L实例安装git三、华为云云耀云服务器L实例git配置1.创建文件用于存放公钥2.设置文件权限3.配置本地公钥 四、华为云云耀云服务器L实例部署git仓库四、git仓库到本地总结 前言 之前一直想搭建一个属于自…...

苹果CMS主题 MXonePro二开优化修复开源版影视网站源码

MXPro模板主题(又名&#xff1a;mxonepro)是一款基于苹果cms程序的一款全新的简洁好看UI的影视站模板类似于西瓜视频&#xff0c;不过同对比MxoneV10魔改模板来说功能没有那么多,也没有那么大气&#xff0c;但是比较且可视化功能较多简洁且有周更记录样式等多功能后台设置&…...

【新版】系统架构设计师 - 软件架构设计<轻量级架构>

个人总结&#xff0c;仅供参考&#xff0c;欢迎加好友一起讨论 文章目录 架构 - 软件架构设计&#xff1c;轻量级架构&#xff1e;考点摘要轻量级架构表示层业务逻辑层持久层数据库 SSH与SSMORMHibernate与Mybatis 架构 - 软件架构设计&#xff1c;轻量级架构&#xff1e; 考点…...

系统架构设计专业技能 ·结构化需求分析 - 数据流图

现在的一切都是为将来的梦想编织翅膀&#xff0c;让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in reality. 点击进入系列文章目录 系统架构设计高级技能 结构化需求分析 - 数据流图 一、数据流图的基本概念二、需…...

linux内核分析:线程和进程创建,内存管理

lec18-19:进程与线程创建 lec20-21虚拟内存管理 内核代码,全局变量这些只有一份,但是内核栈有多份,这可能就是linux线程模型1对1模式的由来。通过栈来做的 x86 CPU支持分段和分页(平坦内存模式)两种 分段,选择子那里就有特权标记了...

SpringMvc根据返回值类型不同处理响应

目录 一、介绍 二、返回值为void &#xff08;1&#xff09;控制层方法 三、返回值为String &#xff08;1&#xff09;控制层 四、返回值为ModelAndView &#xff08;1&#xff09;控制层方法 &#xff08;2&#xff09;jsp页面 一、介绍 我们可以通过控制器方法的返回…...

jq命令安装与使用

目录 一、简介二、下载及安装1.Linux 安装2.Windows 安装3.测试安装结果 三、jq用法1.基本语法2.常见用法1&#xff09;格式化 JSON2&#xff09;获取属性3&#xff09;属性不存在情况处理4&#xff09;数组遍历、截取、展开5&#xff09;管道、逗号、加号6&#xff09;数据构造…...

网络面试题汇总

简述 TCP 连接的过程&#xff08;淘系&#xff09; 参考答案&#xff1a; TCP 协议通过三次握手建立可靠的点对点连接&#xff0c;具体过程是&#xff1a; 首先服务器进入监听状态&#xff0c;然后即可处理连接 第一次握手&#xff1a;建立连接时&#xff0c;客户端发送 syn 包…...

Java————初始集合框架

一 、 集合框架 Java 集合框架Java Collection Framework &#xff0c;又被称为容器container &#xff0c; 是定义在 java.util 包下的一组接口interfaces 和其实现类classes 。 其主要表现为将多个元素element 置于一个单元中&#xff0c; 用于对这些元素进行快速、便捷的存…...

SpringMvc如何向context域设置数据

目录 &#xff08;1&#xff09;控制层方法 &#xff08;2&#xff09;jsp页面 context作用域表示在整个应用范围都有效。在SpringMVC中对context作用域传值&#xff0c;只能使用ServletContext对象来实现。但是该对象不能直接注入到方法参数中&#xff0c;需要通过HttpSessi…...

深入探索智能问答:从检索到生成的技术之旅

目录 一、智能问答概述1. **语义理解**2. **知识库和数据库**3. **上下文感知**4. **动态学习和自适应** 二、发展历程1. **基于规则的系统**2. **统计方法的兴起**3. **深度学习和神经网络的突破**4. **预训练模型** 三、智能问答系统的主要类型四、基于知识库的问答系统五、基…...

OpenClaw对接GLM-4.7-Flash:模型性能优化指南

OpenClaw对接GLM-4.7-Flash&#xff1a;模型性能优化指南 1. 为什么需要专门优化GLM-4.7-Flash的对接&#xff1f; 上个月我在本地部署了OpenClawGLM-4.7-Flash组合&#xff0c;原本期待它能流畅处理我的自动化办公需求&#xff0c;结果遭遇了典型的"水土不服"症状…...

如何在ESXi 6.7上完美驱动Realtek RTL8125网卡:完整编译与部署指南

如何在ESXi 6.7上完美驱动Realtek RTL8125网卡&#xff1a;完整编译与部署指南 【免费下载链接】r8125-esxi Realtek RTL8125 driver for ESXi 6.7 项目地址: https://gitcode.com/gh_mirrors/r8/r8125-esxi 想要在VMware ESXi 6.7服务器上使用Realtek RTL8125网卡&…...

收藏 | 小白程序员必看:轻松入门RAG技术,让大模型拥有你的专业知识领域

收藏 | 小白程序员必看&#xff1a;轻松入门RAG技术&#xff0c;让大模型拥有你的专业知识领域 本文介绍了RAG&#xff08;检索增强生成&#xff09;技术&#xff0c;一种经济高效地解决大模型缺乏特定领域知识的方案。文章详细阐述了RAG的工作流程&#xff1a;用户请求→查询资…...

康威生命游戏中的简易CPU设计与实现

生命游戏中的简易CPU - 第4部分 这是关于在生命游戏中创建数字逻辑门系列文章的第四篇。前几篇文章从如何创建数字逻辑门开始&#xff0c;并利用它们来构建简单的电路。在这篇文章中&#xff0c;我们将实际构建第一台真正的计算机&#xff1a;一个&#xff08;2级流水线&#x…...

论文降AI率要花多少钱?2026主流降AI工具收费标准对比

论文降AI率要花多少钱&#xff1f;2026主流降AI工具收费标准对比 “降一次AI率要好几百&#xff0c;太贵了吧&#xff1f;” “隔壁寝室用的那个才几十块&#xff0c;不知道靠不靠谱。” “有没有免费的降AI工具&#xff1f;” 每年毕业季&#xff0c;这些问题都会在各个论文交…...

NaViL-9B图文对话教程:上传图片即问即答,新手零基础快速上手

NaViL-9B图文对话教程&#xff1a;上传图片即问即答&#xff0c;新手零基础快速上手 1. 认识NaViL-9B&#xff1a;你的智能图文助手 NaViL-9B是一款强大的多模态大语言模型&#xff0c;它能同时理解文字和图片内容。想象一下&#xff0c;你有一个既能聊天又能"看"图…...

AI自动化测试:从工具颠覆到价值重生

一、效率革命&#xff1a;AI如何重构测试工作流1. 用例生成的范式跃迁认知生成技术&#xff1a;基于LLM的需求解析引擎&#xff08;如Testim、Appvance&#xff09;将PRD转化为覆盖核心路径与异常流的测试矩阵。某电商平台实践显示&#xff0c;新功能测试用例生成效率提升20倍&…...

工业上位机开发实战:基于.NET 6和CIP协议,5分钟搞定与ControlLogix PLC的数据对接

工业上位机开发实战&#xff1a;基于.NET 6和CIP协议快速对接ControlLogix PLC 在工业自动化领域&#xff0c;高效可靠的数据采集系统是智能制造的核心枢纽。本文将带您探索如何利用最新的.NET 6技术栈&#xff0c;在5分钟内构建与罗克韦尔ControlLogix系列PLC的通信桥梁。不同…...

医疗AI实战:用OpenCLIP训练自己的医学影像描述生成模型(附完整代码)

医疗AI实战&#xff1a;用OpenCLIP训练医学影像描述生成模型的全流程解析 当放射科医生面对堆积如山的CT扫描片时&#xff0c;能否有一个AI助手自动生成初步诊断描述&#xff1f;这个看似科幻的场景&#xff0c;正通过多模态深度学习变为现实。本文将手把手带您实现一个能理解医…...

SAP FI模块实战:OBA1事务码配置外币评估自动过账(附T030S表解析)

SAP FI模块外币评估自动过账实战指南&#xff1a;OBA1配置与T030S表深度解析 在国际化业务场景中&#xff0c;企业经常需要处理多币种交易&#xff0c;外币评估是财务会计周期性的重要工作。本文将带您深入掌握SAP系统中外币评估自动过账的核心配置&#xff0c;不仅提供OBA1事务…...