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

【CSDN 每日一练 ★★☆】【动态规划】最小路径和

【CSDN 每日一练 ★★☆】【动态规划】最小路径和

动态规划

题目

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例

示例 1:

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

示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12

提示
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100
思路
  • 动态规划
Java实现
public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int sum = 0;if (m < 1 || n < 1) // grid不存在return 0;if (m == 1) { //只有一行for (int i = 0; i < n; i++) {sum = sum + grid[0][i];}return sum;}if (n == 1) { //只有一列for (int i = 0; i < m; i++) {sum = sum + grid[i][0];}return sum;}int[][] dp = new int[m][n];dp[0][0] = grid[0][0];// 初始化第一列for (int k = 1; k < m; k++) {dp[k][0] = grid[k][0] + dp[k - 1][0];}// 初始化第一行for (int l = 1; l < n; l++) {dp[0][l] = grid[0][l] + dp[0][l - 1];}// 处理DP状态方程 dp(i,j) = grid(i,j)+MIN(dp(i-1,j),dp(i,j-1))for (int k = 1; k < m; k++) {for (int l = 1; l < n; l++) {dp[k][l] = grid[k][l] + Math.min(dp[k - 1][l], dp[k][l - 1]);}}return dp[m - 1][n - 1];
}

相关文章:

【CSDN 每日一练 ★★☆】【动态规划】最小路径和

【CSDN 每日一练 ★★☆】【动态规划】最小路径和 动态规划 题目 给定一个包含非负整数的 m x n 网格 grid &#xff0c;请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 说明&#xff1a;每次只能向下或者向右移动一步。 示例 示例 1&#x…...

前端学习之webpack的使用

概述 webpack是一个流行的前端项目构建工具&#xff08;打包工具&#xff09;&#xff0c;可以解决当前web开发中所面临的问题。 webpack提供了友好的模块化支持&#xff0c;以及代码压缩混淆、处理js兼容问题、性能优化等强大的功能&#xff0c;从而让程序员把工作重心放到具…...

【java学习—十一】泛型(1)

文章目录 1. 为什么要有泛型Generic2. 泛型怎么用2.1. 泛型类2.2. 泛型接口2.3. 泛型方法 3. 泛型通配符3.1. 通配符3.2. 有限制的通配符 1. 为什么要有泛型Generic 泛型&#xff0c;JDK1.5新加入的&#xff0c;解决数据类型的安全性问题&#xff0c;其主要原理是在类声明时通过…...

CN考研真题知识点二轮归纳(4)

持续更新&#xff0c;上期目录&#xff1a; CN考研真题知识点二轮归纳&#xff08;4&#xff09;https://blog.csdn.net/jsl123x/article/details/134135134?spm1001.2014.3001.5501 1.既可以扩展网段又是二层的设备 网段一般指一个计算机网络中使用同一物理层设备&#xff…...

ROS学习笔记(4):ROS架构和通讯机制

前提 前4篇文章以及帮助大家快速入门ROS了&#xff0c;而从第5篇开始我们会更加注重知识积累。同时我强烈建议配合B站大学的视频一起服用。 1.ROS架构三层次&#xff1a; 1.基于Linux系统的OS层&#xff1b; 2.实现ROS核心通信机制以及众多机器人开发库的中间层&#xff1b…...

深度新闻稿件怎么写?新闻稿怎么写得有深度?

深度新闻稿件&#xff0c;顾名思义&#xff0c;是对新闻事件进行深入挖掘和分析的稿件。它不仅仅是对事件的简单报道&#xff0c;更注重对事件背后的社会现象、原因、影响等方面进行深度剖析&#xff0c;从而使读者能够全面、深入地了解事件。这种稿件要求作者具备较高的新闻敏…...

百度智能云千帆大模型平台黑客马拉松报名开启!

比赛简介 创造是生成式 AI 的核心。无论是智能导购带来的线上购物体验升级&#xff0c;还是主图生成带来的素材生产效率提升&#xff0c;又或是游戏场景的快速设置、智能 NPC 的全新交互、数字广告的精准推荐和个性化定制&#xff0c;亦或者是为学生提供更符合真实的口语练习环…...

数据库 | 看这一篇就够了!最全MySQL数据库知识框架!

大家好&#xff01; 作为一名程序员&#xff0c;每天和各种各样的“数据库”打交道&#xff0c;已经成为我们的日常。当然&#xff0c;立志成为一名超级架构师的我&#xff0c;肯定要精通这项技能。咳咳&#xff01;不过饭还是要一口一口吃的&#xff0c;“数据库”这个内容实在…...

Android 控件背景实现发光效果

主要实现的那种光晕效果&#xff1a;中间亮&#xff0c;四周逐渐变淡的。 这边有三种发光效果&#xff0c;先上效果图。 第一种、圆形发光体 实现代码&#xff1a;新建shape_light.xml&#xff0c;导入以下代码。使用时&#xff0c;直接给view设置为background。 <?xml …...

安全狗亮相厦门市工信领域数据安全宣贯培训会

10月31日&#xff0c;厦门市工业和信息化局&#xff08;市大数据管理局&#xff09;顺利举办厦门市工信领域数据安全宣贯培训。 作为国内云原生安全领导厂商&#xff0c;安全狗以厦门市工业领域数据安全管理支撑单位身份受邀出席此次会议。 据悉&#xff0c;此次活动旨在贯彻…...

最长回文子串

问题 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同&#xff0c;则该字符串称为回文字符串。 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#xff1a;"bab" 解释&#xff1a;"aba" 同…...

从瀑布模式到水母模式:ChatGPT引领软件研发的革新之路

ChatGPT引领软件研发的革新之路 概述操作建议本书优势 内容简介作者简介专家推荐读者对象目录直播预告写在末尾&#xff1a; 主页传送门&#xff1a;&#x1f4c0; 传送 概述 计算机技术的发展和互联网的普及&#xff0c;使信息处理和传输变得更加高效&#xff0c;极大地改变了…...

一种使用wireshark快速分析抓包文件amr音频流的思路方法

解决方案&#xff1a; 1. 使用wireshark过滤amr,并导出原始数据文件&#xff1b; 2.使用ue的二进制编辑模式&#xff0c;编辑该文件&#xff0c;添加amr头&#xff0c;6个字节数据“#!AMR”&#xff0c;字节数据为 23 21 41 4D 52 0A 3.修正格式&#xff1a;通过抓包发现&#…...

银河麒麟x86版、银河麒麟arm版操作系统编译zlmediakit

脚本 # 安装依赖 gcc-c.x86_64 这个不加的话会有问题 sudo yum -y install gcc gcc-c libssl-dev libsdl-dev libavcodec-dev libavutil-dev ffmpeg git openssl-devel gcc-c.x86_64mkdir -p /home/zenglg cd /home/zenglg git clone --depth 1 https://gitee.com/xia-chu…...

InnoDB - 双写机制

双写机制用于提高数据持久性和可靠性。 双写机制的核心思想是&#xff0c;将写操作先写入一个临时缓冲区&#xff0c;然后再写入实际的数据文件。这个临时缓冲区通常是固定大小的内存缓冲区&#xff0c;称为双写缓冲。这个机制的主要目的是避免数据文件在写入时出现损坏或数据…...

【蓝桥杯选拔赛真题08】C++最大值最小值平均值 青少年组蓝桥杯C++选拔赛真题 STEMA比赛真题解析

目录 C/C++最大值最小值平均值 一、题目要求 1、编程实现 2、输入输出 二、算法分析</...

软考高级系统架构设计师系列之:系统开发基础知识、项目管理、信息安全和网络安全、计算机网络章节选择题详解

软考高级系统架构设计师系列之:系统开发基础知识、项目管理、信息安全和网络安全、计算机网络章节选择题详解 一、产品配置二、需求管理三、需求跟踪四、软件生命周期五、RUP六、耦合与内聚七、软件文档八、软件需求九、软件活动十、项目时间管理十一、需求管理十二、项目范围…...

0基础学习PyFlink——时间滑动窗口(Sliding Time Windows)

在《0基础学习PyFlink——时间滚动窗口(Tumbling Time Windows)》我们介绍了不会有重复数据的时间滚动窗口。本节我们将介绍存在重复计算数据的时间滑动窗口。 关于滑动窗口&#xff0c;可以先看下《0基础学习PyFlink——个数滑动窗口&#xff08;Sliding Count Windows&#x…...

API安全之《大话:API的前世今生》

写在前面&#xff1a;本文结合API使用的业界现状&#xff0c;系统性地阐述API的基本概念、发展历史、表现形式等基础内容&#xff0c;主要包含以下内容&#xff1a; 1.什么是API 2.API的发展历史 3.现代API常用消息格式 4.top N 互联网企业API 使用现状 当前的世界是一个信…...

H5或者Vue实现二维码识别

前言 1、扫码识别库采用开源的zxing/library 2、支持js&#xff0c;Vue&#xff0c;lit等实现 原文章地址和代码仓库地址 1、在界面创建video标签用来显示摄像头内容 <!-- 视区 --><!-- lit写法 --> <video ${ref(this.videoRef)} class"xy-scan-wrap…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...