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

leetcode64 最小路径和

题目

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。

示例

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

解析

这道题现在看来会相对简单一些,使用动规五部曲直接分析一下就行
1.dp数组及其含义
dp[i][j]表示走到grid[i][j]的时候最小路径和为dp[i][j]
2.递推公式
题目中说了只能向下或者向右,那么就是:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3.初始化
除了dp[0][0]需要初始化之外,第一行和第一列也需要初始化,

func minPathSum(grid [][]int) int {if len(grid) == 0 || len(grid[0]) == 0 {return 0}m := len(grid)n := len(grid[0])dp := make([][]int, m+1)for i := 0; i <= m; i++ {dp[i] = make([]int, n+1)}dp[0][0] = grid[0][0]for i := 1; i < m; i++ { // 第一行初始化dp[i][0] = dp[i-1][0] + grid[i][0]}for j := 1; j < n; j++ { // 第一列初始化dp[0][j] = dp[0][j-1] + grid[0][j]}for i := 1; i < m; i++ {for j := 1; j < n; j++ {dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] // 递推公式}}return dp[m-1][n-1]
}func min(a, b int) int {if a > b {return b}return a
}

相关文章:

leetcode64 最小路径和

题目 给定一个包含非负整数的 m x n 网格 grid &#xff0c;请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 说明&#xff1a;每次只能向下或者向右移动一步。 示例 输入&#xff1a;grid [[1,3,1],[1,5,1],[4,2,1]] 输出&#xff1a;7 解释&a…...

金盘图书馆微信管理后台信息泄露漏洞 复现

金盘图书馆微信管理后台信息泄露漏洞 复现 0x01 前言 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果…...

nginx实现负载均衡(三)

之前说过大部分我们用到的配置都是在http模块中配置的&#xff0c;这里要实现的负载均衡也是一样的&#xff0c;要在http模块中的http全局块中指定&#xff0c;这里我们先给出一个例子 demo #user nobody; worker_processes 1;#error_log logs/error.log; #error_log log…...

Android---深入理解ClassLoader的加载机制

目录 Java 中的 ClassLoader 1. APPClassLoader 系统类加载器 2. ExtClassLoader 扩展类加载器 3. BootstrapClassLoader 启动类加载器 双亲委派模式(Parents Delegation Model) Android 中的 ClassLoader 1. PathClassLoader 2. DexClassLoader 总结 一个完整的 Java…...

超自动化加速落地,助力运营效率和用户体验显著提升|爱分析报告

RPA、iPaaS、AI、低代码、BPM、流程挖掘等在帮助企业实现自动化的同时&#xff0c;也在构建一座座“自动化烟囱”。自动化工具尚未融为一体&#xff0c;协同价值没有得到释放。Gartner于2019年提出超自动化&#xff08;Hyperautomation&#xff09;概念&#xff0c;主要从技术组…...

Linux posix_spawn和fork的区别

posix_spawn和fork都是用于在Linux中创建新进程的函数&#xff0c;但它们的工作方式有所不同。posix_spawn它的工作方式类似于fork()后跟exec()。 fork&#xff1a;fork函数创建一个新的进程&#xff0c;该进程是调用进程的一个副本。这意味着除了必要的启动资源外&#xff0c;…...

聊聊分布式架构02——Http到Https

目录 HTTP通信协议 请求报文 响应报文 持久连接 状态管理 HTTPS通信协议 安全的HTTPS HTTP到HTTPS的演变 对称加密 非对称加密 混合加密机制 证书机构 SSL到底是什么 HTTPS是身披SSL外壳的HTTP HTTP通信协议 一次HTTP请求的通信流程&#xff1a;客户端浏览器通过…...

1024 画跳动的爱心#程序代码 #编程语言 #计算机

废话不多说 直接开干! 用到库 random time tkinter 快速镜像 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple tkinter 上代码 import random import time from math import sin, cos, pi, log from tkinter import *CANVAS_WIDTH 640 # 画布的宽 CANVAS_HEIGH…...

【排序算法】堆排序详解与实现

一、堆排序的思想 堆排序(Heapsort)是指利用堆积树&#xff08;堆&#xff09;这种数据结构所设计的一种排序算法&#xff0c;它是选择排序的一种。它是通过堆&#xff08;若不清楚什么是堆&#xff0c;可以看我前面的文章&#xff0c;有详细阐述&#xff09;来进行选择数据&am…...

java Spring Boot整合jwt实现token生成

先在 pom.xml 文件中注入依赖 <!-- JWT --> <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt-api</artifactId><version>0.11.2</version> </dependency> <dependency><groupId>io.jsonw…...

如何使用Git和GitHub进行版本控制

如何使用Git和GitHub进行版本控制 版本控制是软件开发过程中的重要组成部分&#xff0c;它允许开发者跟踪和管理代码的变化&#xff0c;以确保团队协作顺畅&#xff0c;并帮助在需要时回溯到以前的代码状态。Git和GitHub是最流行的版本控制工具之一&#xff0c;本文将介绍如何…...

彻底解决 WordPress cURL error 28 错误

cURL 连接超时。 这种情况最普遍&#xff0c;这里的超时并不是完全不可连接&#xff0c;而是因为网络状况或其它原因数据传输缓慢&#xff0c;超过连接的时间限制导致传输中断引起的错误。 不论是何种原因导致连接超时&#xff0c;都可以通过增加超时限制来解决此问题。但 UR…...

LLM项目代码改写

背景&#xff1a; 最近在做代码大语言模型生成项目代码的课题。代码生成现在大部分的工作是在做即时代码生成&#xff0c;这个有点类似代码智能提示&#xff0c;只不过生成的可能是一段片段代码&#xff1b;然而对于整个项目代码的生成做的团队并不多&#xff0c;原因大致如下…...

小谈设计模式(14)—建造者模式

小谈设计模式&#xff08;14&#xff09;—建造者模式 专栏介绍专栏地址专栏介绍 建造者模式角色分类产品&#xff08;Product&#xff09;抽象建造者&#xff08;Builder&#xff09;具体建造者&#xff08;Concrete Builder&#xff09;指挥者&#xff08;Director&#xff0…...

【kubernetes】k8s中的选主机制

leader-election选主机制 1 为什么需要leader-election&#xff1f; 在集群中存在某种业务场景&#xff0c;一批相同功能的进程同时运行&#xff0c;但是同一时刻&#xff0c;只能有一个工作&#xff0c;只有当正在工作的进程异常时&#xff0c;才会由另一个进程进行接管。这…...

学生选课系统基础版

第四章java中的集合框架 4.1&#xff1a;java中的集合框架概述 1.java概念与作用 现实中很多事物凑在一起都是集合 如购物车是商品的集合 军队呢 是军人的集合 学校是学生的结合 数学中的集合&#xff1a; 具有共同属性的事物的总体 java中的集合类呢 跟数学的集…...

redis no-appendfsync-on-rewrite

no-appendfsync-on-rewriteyes 当用户请求写入redis的时候&#xff0c;这部分数据只是保存在内存中&#xff0c;主线程并不会马上对此数据进行 aof刷盘&#xff08;而是根据aof刷盘的频率由子线程进行同步&#xff09;&#xff0c;这样子不会阻塞但是会导致数据丢失no-appendfs…...

Spring Cloud Gateway2之路由详解

Spring Cloud Gateway路由 文章目录 1. 前言2. Gateway路由的基本概念3. 三种路由1. 静态路由2. 动态路由1. 利用外部存储2. API动态路由 3. 服务发现路由(自动路由)3.1. 配置方式3.2 自动路由&#xff08;服务发现&#xff09;原理核心源码GatewayDiscoveryClientAutoConfigur…...

阿里云RDS关系型数据库详细介绍_多版本数据库说明

阿里云RDS关系型数据库大全&#xff0c;关系型数据库包括MySQL版、PolarDB、PostgreSQL、SQL Server和MariaDB等&#xff0c;NoSQL数据库如Redis、Tair、Lindorm和MongoDB&#xff0c;阿里云百科分享阿里云RDS关系型数据库大全&#xff1a; 目录 阿里云RDS关系型数据库大全 …...

Vue中的数据绑定

一、v-bind单向数据绑定 单向数据绑定中&#xff0c;数据只能由data流向页面。 v-bind:属性名"data变量" 或简写为 :属性名"data变量" 我们修改data中的iptvalue值&#xff0c;页面input框中的value值改变。 而我们修改input框中的value值&#xff0…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

python打卡第47天

昨天代码中注意力热图的部分顺移至今天 知识点回顾&#xff1a; 热力图 作业&#xff1a;对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图&#xff0c;展示模…...

使用python进行图像处理—图像滤波(5)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...

成工fpga(知识星球号)——精品来袭

&#xff08;如需要相关的工程文件请关注知识星球&#xff1a;成工fpga&#xff0c;https://t.zsxq.com/DMeqH&#xff0c;关注即送200GB学习资料&#xff0c;链接已置顶&#xff01;&#xff09; 《孩子都能学会的FPGA》系列是成工完成的第一个系列&#xff0c;也有一年多的时…...

matlab实现DBR激光器计算

DBR激光器计算程序。非常值得参考的程序。DBR激光器程序 DBR计算/1.txt , 2056 DBR计算/4.asv , 22 DBR计算/4.txt , 32 DBR计算/GetDeviceEfficiency.asv , 2012 DBR计算/GetDeviceEfficiency.m , 2014 DBR计算/GetOneLayerArray.asv , 837 DBR计算/GetOneLayerArray.m , 836…...

vb监测Excel两个单元格变化,达到阈值响铃

需求 在Excel中实现监控两个单元格之间的变化范围&#xff0c;当达到某个设定的值的范围内时&#xff0c;实现自动响铃提示。 实现&#xff1a; 首先设置Excel&#xff0c;开启宏、打开开发者工具&#xff0c;点击visual Basic按钮&#xff0c;然后在左侧双击需要监测的shee…...