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

力扣 最小路径和

又是一道动态规划基础例题。

题目

这道题可以类似不同路径。先把左上角格子进行填充,然后用一个数组去更新每走到一个格的数字总和,首先处理边界问题,把最左边的列只能由上方的行与原来的格子数值的和,同理,最上方的行只能由作左边的行与原来的格子数值的和,然后像上次路径dp那样做遍历,直到取出右下角的坐标的数值即可。

class Solution {public int minPathSum(int[][] grid) {// f[m][n] = Math.min(f[m-1][n],f[m][n-1]) + grid[m][n]int m = grid.length ;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0] = grid[0][0];for ( int i = 1 ; i < m ; i++ ) {dp[i][0] = grid[i][0]+dp[i-1][0];}for ( int i = 1 ; i < n ; i++ ) {dp[0][i] = grid[0][i] + dp[0][i-1];}for ( int i = 1 ;  i < m ;  i++ ) {for ( int j = 1 ; j < n ; j++ ) {dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);}}return dp[m-1][n-1];}
}

也可以优化成滚动数组。

class Solution {public int minPathSum(int[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int rows = grid.length, columns = grid[0].length;// 创建一个一维数组 dp 来存储每一行的路径和int[] dp = new int[columns];dp[0] = grid[0][0]; // 起点处的最小路径和for (int j = 1; j < columns; j++) {dp[j] = dp[j - 1] + grid[0][j];}for (int i = 1; i < rows; i++) {// 第一列的位置,路径只能从上方来dp[0] += grid[i][0];for (int j = 1; j < columns; j++) {dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];}}// 最终的结果在 dp[columns - 1] 中,表示右下角的最小路径和return dp[columns - 1];}
}

典型路径动态规划,助你找准最好的路径。 

相关文章:

力扣 最小路径和

又是一道动态规划基础例题。 题目 这道题可以类似不同路径。先把左上角格子进行填充&#xff0c;然后用一个数组去更新每走到一个格的数字总和&#xff0c;首先处理边界问题&#xff0c;把最左边的列只能由上方的行与原来的格子数值的和&#xff0c;同理&#xff0c;最上方的行…...

Scala中的可变Map操作:简单易懂指南 #Scala Map #Scala

引言 在编程中&#xff0c;Map是一种常见的数据结构&#xff0c;用于存储键值对。Scala提供了不可变Map和可变Map两种类型&#xff0c;它们在处理数据时有不同的特性和用途。本文将通过一个简单的示例&#xff0c;带你了解Scala中可变Map的基本操作&#xff0c;包括添加元素、…...

【go从零单排】XML序列化和反序列化

&#x1f308;Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 &#x1f4d7;概念 在 Go 语言中&#xff0c;处理 XML 数据主要使用 encoding/xml 包。这个包提供了…...

在 Oracle Linux 8.9 上安装Oracle Database 23ai 23.5

在 Oracle Linux 8.9 上安装Oracle Database 23ai 23.5 1. 安装 Oracle Database 23ai2. 连接 Oracle Database 23c3. 重启启动后&#xff0c;手动启动数据库4. 重启启动后&#xff0c;手动启动 Listener5. 手动启动 Pluggable Database6. 自动启动 Pluggable Database7. 设置开…...

在 Ubuntu 上安装 `.deb` 软件包有几种方法

在 Ubuntu 上安装 .deb 软件包有几种方法&#xff0c;可以使用命令行工具&#xff0c;也可以通过图形界面进行安装。以下是几种常见的安装方法&#xff1a; 方法 1&#xff1a;使用 dpkg 命令安装 .deb 包 打开终端。 使用 dpkg 命令安装 .deb 包&#xff1a; sudo dpkg -i /…...

一文了解Android本地广播

在 Android 开发中&#xff0c;本地广播&#xff08;Local Broadcast&#xff09;是一种轻量级的通信机制&#xff0c;主要用于在同一应用进程内的不同组件之间传递消息&#xff0c;而无需通过系统的全局广播机制。这种方法既可以提高安全性&#xff08;因为广播仅在应用内传播…...

Ingress nginx 公开TCP服务

文章目录 背景搞起拓展( PROXY Protocol )参考 背景 公司业务繁多&#xff0c; HTTP、GRPC、TCP多种协议服务并存&#xff0c;Kubernetes流量入口复杂&#xff0c;所以萌生了通过LoadBalancer Ingress-nginx 的方式完全的结果入口流量&#xff0c;当然在高并发的场景下可以对…...

谷歌浏览器支持的开发者工具详解

谷歌浏览器&#xff08;Google Chrome&#xff09;是全球最受欢迎的网页浏览器之一&#xff0c;它不仅提供了快速、安全的浏览体验&#xff0c;还为开发者提供了强大的开发者工具。本文将详细介绍如何使用谷歌浏览器的开发者工具&#xff0c;并解答一些常见问题。&#xff08;本…...

【数据结构】汇编 、机器语言 高级语言 简析。

汇编语言、机器语言和高级语言 1. 机器语言&#xff08;Machine Language&#xff09; 定义&#xff1a;机器语言是计算机能够直接执行的、用二进制编码的指令集&#xff0c;属于最低级别的编程语言。它由 0 和 1 组成&#xff0c;每条指令由一串二进制数表示。机器语言与计算…...

【青牛科技】GC3901,强势替代 A3901/ALLEGRO应用于摇头机等产品中

在电子工程的浩瀚世界里&#xff0c;不断追求更优性能、更高效率和更低成本的芯片解决方案&#xff0c;是每一位电子工程师的不懈目标。今天&#xff0c;我们要为大家隆重介绍一款足以让你眼前一亮的芯片 —— 芯麦 GC3901&#xff0c;它将以强大的实力成为 A3901/ALLEGRO 的完…...

Java API类与接口:类的转换方法与正则表达式

文章目录 Java包装类的概述对应包装类包装类的转换方法&#xff08;parse)Integer.parseInt(String s)Long.parseLong(String s)Byte.parseByte(String s)Short.parseShort(String s)Float.parseFloat(String s)Double.parseDouble(String s) 正则表达式常用方法 字符规则. 匹配…...

OceanBase JDBC (Java数据库连接)的概念、分类与兼容性

本章将介绍 OceanBase JDBC的 概念与分类&#xff0c;已帮助使用 JDBC 的用户及技术人员更好的 了解JDBC&#xff0c;以及 OceanBase JDBC在与 MySQL 及 Oracle 兼容性方面的相关能力。 一、JDBC 基础 1.1 JDBC 的概念 JDBC 一般指 Java 数据库连接。Java 数据库连接&#xf…...

Linux服务器定时执行jar重启命令

1. sh脚本编写 appNamecvcp-weather PIDps -ef |grep java | grep $appName | grep -v grep | awk {print $2} if [ "$PID" "" ]; thensleep 1;echo "no process";elseecho "process exsits";kill -9 $PID fi sleep 2s nohup /usr/l…...

速览!Win11 22H2/23H2 11月更新补丁KB5046633发布!

系统之家11月13日报道消息&#xff0c;微软为Win11 22H2和23H2用户发布了11月更新补丁KB5046633。此次更新后&#xff0c;系统版本号提升至22621.4460和22631.4460。该补丁包含多项改进和修复&#xff0c;有助于提升用户的使用体验感。想了解完整内容的小伙伴&#xff0c;请继续…...

A day a tweet(sixteen)——The better way of search of ChatGPT

Introducing ChatGPT search a/ad.及时的/及时地 ChatGPT can now search the web in a much better way than before so you get fast, timely a.有关的(relative n.亲戚,亲属;同类事物 a.比较的&#xff1b;相对的) answers with link…...

【网络】HTTP 协议

目录 基本概念基于 HTTP 的系统组成HTTP 的基本性质 HTTP 请求头 & 响应头HTTP 的请求方法HTTP 的返回码HTTP 的 CookieHTTP 缓存 Cache-Control会话HTTP/1.x 的连接管理 基本概念 HTTP&#xff08;Hypertext Transfer Protocol&#xff0c;超文本传输协议&#xff09;是一…...

git push报错 unexpected disconnect while reading sideband packet

应该是缓冲不够引起的&#xff0c;可以使用以下命令增加缓存&#xff1a; git config --global http.postBuffer 1048576000 1048576000这里的单位是Byte, 也就是1G。 亲测可以了...

JSX 语法与基础组件使用

在 React Native 中&#xff0c;JSX 是一种 JavaScript 的语法扩展&#xff0c;用于描述 UI 界面。JSX 语法类似于 HTML&#xff0c;但它是 JavaScript 的语法糖&#xff0c;可以直接在 JavaScript 代码中编写 UI 组件。本章节将介绍 JSX 语法的基础知识&#xff0c;以及 React…...

ReactPress:构建高效、灵活、可扩展的开源发布平台

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎Star。 在当今数字化时代&#xff0c;内容管理系统&#xff08;CMS&#xff09;已成为各类网站和应用的核心组成部分。ReactPress&#xff0c;作为一款融合了现代Web开发多项先进技术的开…...

emulator总结

什么是硬件仿真器 做IC设计的人应该都知道软件仿真和FPGA原型验证&#xff0c;可以把硬件仿真器理解为这二者之间的产物&#xff0c;它同时具备二者的优点。 软件仿真&#xff08;simulator&#xff09;全面&#xff0c;支持UVM、assert、coverage收集、可以很方便的dump 波形…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...