【LeetCode】【算法】64. 最小路径和

LeetCode 64. 最小路径和

题目描述

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

思路

思路:这种题太典了,典型一眼看破的动态规划,当前最小路径和由min(上面一格最小路径和,左边一格最小路径和)+grid[i][j]组成。需要做的就是:

  1. 判断当前这一格的上侧和左侧是否都存在,若存在则dp[i][j]=grid[i][j]+Math.min(dp[i-1][j], dp[i][j-1])
  2. 若只有上侧存在则dp[i][j]=dp[i-1][j]+grid[i][j]
  3. 若只有左侧存在则dp[i][j]=dp[i][j-1]+grid[i][j]
  4. 若都不存在(也就是左上角的情况)dp[i][j]=grid[i][j]

代码

class Solution {public int minPathSum(int[][] grid) {int[][] dp = new int[grid.length][grid[0].length];for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (i - 1 >= 0 && j - 1 >= 0){dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);} else if (i - 1 >= 0) {dp[i][j] = grid[i][j] + dp[i-1][j];} else if (j - 1 >= 0) {dp[i][j] = grid[i][j] + dp[i][j-1];} else {dp[i][j] = grid[i][j];}}}return dp[grid.length - 1][grid[0].length - 1];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/12905.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

win11安装wsa 安卓

今天和大家分享一个如何在windows10/11/12操作系统上使用Windows Subsystem for Android安卓APK应用系统的教程&#xff1b;网络上有很多教程&#xff0c;但是来回折腾很久也是各种问题&#xff0c;经过研究&#xff0c;找到一套完整有效的方案&#xff1b; 第一步、进入系统设…

美食网的设计与实现

摘 要 随着科技的发展、生活水平的提升&#xff0c;人们更加注重饮食搭配和饮食健康。通过网络技术来加强美食与健康知识的普及是当前一种可行的措施。通过网页浏览美食网&#xff0c;不仅可以普及每道美食的做法&#xff0c;通过制作美食来缓解心情&#xff0c;还可以通过美…

2024-2025年EI会议时间表,把握未来学术研讨机遇

2024-2025年多场国际学术会议将在中国多地举办&#xff0c;涵盖网络、通信、AI等领域&#xff0c;均支持EI等检索。会议时间、地点及检索信息已提供&#xff0c;涉及北京、淮北、深圳等城市。 以下是部分精品学术会议基本信息&#xff0c;欢迎点击链接查看&#xff1a; 第二届…

QML —— 圆形波浪进度条控件(附上源码)

效果 说明 QML中使用画布元素(canvas element),使用画布元素可画出各种各样的图形,同时允许脚本绘制。画布元素提供了一个依赖于分辨率的位图画布,也可以使用JavaScript脚本来绘制图形,制作游戏或者其它的动态图像。QML中的画布元素是基于HTML5的画布元素来完成的。    …

echarts引入自定义字体不起作用问题记录

echarts引入自定义字体不起作用问题记录 1、问题描述 初始化界面字体不作用&#xff0c;当界面更新后字体样式正常显示 2、原因描述 这通常是由于字体文件加载延迟导致的。ECharts 在初始化时可能还没有加载完字体文件&#xff0c;因此无法正确应用字体样式 3、解决方案 …

UE5.4 PCG 生成藤蔓墙体

一、新建Actor&#xff0c;添加Spline组件&#xff0c;挂上PCG组件&#xff0c;设置“墙体”和“植被”为静态网格体变量 二、编写PCG_Wall 1.生成墙体 2.生成墙体植被

【网络】子网掩码

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;了解什么是子网掩码&#xff0c;并且能熟练掌握子网掩码的相关计算。 > 毒鸡汤&#xff1a;有些事情&#xff0c;总是不明白&#xff0c;所以我不会…

Worldly平台更新Higg FEM 2024模块价格及购买指南

近日&#xff0c;LEVERAGE供应链管理从美国可持续服装联盟&#xff08;Cascale&#xff09;验证官方Worldly平台模块订阅更新中获悉&#xff0c;FEM2024模块价格更新的重要信息。此次更新涉及工厂环境模块&#xff08;FEM&#xff09;和工厂社会劳工模块&#xff08;FSLM&#…

Rocky9通过Docker-compose部署zabbix 7.0.5

Rocky9通过Docker-compose部署zabbix 7.0.5 1. 实验环境架构2. Zabbix-Server准备工作2.1 更新仓库2.2 安装docker-ce2.3 安装docker-compose 3. 安装Zabbix项目3.1 克隆项目3.2 预下载镜像3.3 启动Zabbix 4. 启动web管理端4.1 登录web管理页4.2 修改时区和语言 5. Agent安装配…

企业内训系统

在当今这个竞争激烈的市场环境中&#xff0c;企业的持续发展不仅依赖于外部市场的拓展&#xff0c;更离不开内部团队能力的提升。企业内训系统&#xff0c;作为提升企业竞争力、促进员工成长的重要工具&#xff0c;正逐渐成为现代企业管理中不可或缺的一环。本文将深入探讨企业…

QT自定义控件封装

QT自定义控件封装 1.概述 这篇文章介绍如何创建UI文件&#xff0c;通过自定义方式将两个控件联动起来&#xff0c;实现自定义功能。 2.创建UI文件 新建一个widget的普通项目&#xff0c;然后在项目名称上右键选择And New... 新建文件&#xff0c;然后选择QT 再选择Qt Desig…

物联网(RFID)全景:被装信息化监控应用与挑战

一、被装物联网信息化建设的动因 信息化改革在20世纪80年代中期启航&#xff0c;旨在提升被装保障的效率。随着时间的推移&#xff0c;硬件的广泛运用和软件的快速迭代&#xff0c;装备业务在规划、制造、分发以及战时支援等核心环节&#xff0c;已经与信息系统深度融合&#x…

屏幕解析工具——OmniParser

0 引言 OmniParser是微软开源的一种屏幕解析工具&#xff0c;提供了一种将用户界面截图解析为结构化元素的综合方法&#xff0c;通过此方法可以对UI界面进行可交互元素的提取和描述&#xff0c;然后将此结构化信息和任务指令&#xff0c;输入到大模型中&#xff0c;以增强大模…

衡石分析平台系统分析人员手册-嵌入样式定制化指南­

发布页面嵌入样式定制化指南​ 使用衡石智能分析平台制作好 Dashboard 和 Chart 以后&#xff0c;可以通过 iframe 的方式嵌入到已有系统中。为了达到风格统一&#xff0c;嵌入 iframe 的时候支持丰富的定制化选项。 定制 Dashboard 的 iframe​ 参数列表​ 仪表盘嵌入时支持…

Nginx更换ssl证书不生效

一.场景 在用的ssl证书要过期了&#xff0c;申请了新的ssl证书下来&#xff0c;在nginx配置上更换上去后&#xff0c;打开系统地址&#xff0c;一依然是使用原来的旧证书&#xff0c;以前有更换过别的域名证书&#xff0c;重启nginx服务后立马就生效了。 这次没生效&#xff…

基于python和Django的用户管理接口开发

1.异步用户登录\登出接口开发 1.设计公共响应数据类型 文件地址&#xff1a;utils/response404.py from django.http import JsonResponseclass BadRequestJsonResponse(JsonResponse):status_code 400def __init__(self, err_list, *args, **kwargs):data {"error_c…

Docker--Docker是什么和对Docker的了解

Docker 的本质 Docker的本质是LXC&#xff08;Linux容器&#xff09;之类的增强版&#xff0c;它本身不是容器&#xff0c;而是容器的易用工具。 Docker通过虚拟化技术&#xff0c;将代码、依赖项和运行环境打包成一个容器&#xff0c;并利用隔离机制来使得容器之间互相独立、…

Window下PHP安装最新sg11(php5.3-php8.3)

链接: https://pan.baidu.com/s/10yyqTJdwH_oQJnQtWcwIeA 提取码: qz8y 复制这段内容后打开百度网盘手机App&#xff0c;操作更方便哦 (链接失效联系L88467872) 1.下载后解压文件&#xff0c;将对应版本的ixed.xx.win文件放进php对应的ext目录下&#xff0c;如图所示 2.修改ph…

C# yolo10使用onnx推理

一、前言 本篇总结C#端使用yolo10的onnx文件做模型推理&#xff0c;主要使用Microsoft.ML.OnnxRuntime.Gpu这个库。需要注意的是Microsoft.ML.OnnxRuntime 和 Microsoft.ML.OnnxRuntime.Gpu 这2库只装1个就行&#xff0c;CPU就装前者&#xff0c;反之后者。然后需要注意系统安装…

MNIST数据集下载与保存为图片格式

深度学习 文章目录 深度学习下载数据集 下载数据集 https://github.com/geektutu/tensorflow-tutorial-samples/tree/master/mnist/data_set t10k-images-idx3-ubyte.gz t10k-labels-idx1-ubyte.gz train-images-idx3-ubyte.gz train-labels-idx1-ubyte.gz 解压后&#xff0c;…