当前位置: 首页 > 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…...

【限时开源】Polars 2.0清洗模板库V1.0发布:含金融时序对齐、电商ID映射、日志正则归一化等9大高复用Pipeline

第一章&#xff1a;Polars 2.0大规模数据清洗技巧入门到精通教程 Polars 2.0 是专为高性能、内存安全与并行计算设计的 DataFrame 库&#xff0c;其惰性执行引擎与零拷贝语义使其在处理 GB 级别结构化数据时显著优于 Pandas。本章聚焦真实场景下的数据清洗实践&#xff0c;涵盖…...

3分钟拥有自己的零代码平台!敲敲云一键安装全攻略

敲敲云 AI 专题研究 | 敲敲云零代码平台一键部署&#xff0c;让普通人轻松搭建业务系统 还在为技术门槛发愁&#xff1f;还在为复杂的代码开发而烦恼&#xff1f; 今天要给大家介绍一款完全免费的零代码平台 —— 敲敲云。它集成了 AI 应用开发能力&#xff0c;支持一键安装部…...

【FMCW雷达】频率调制连续波FMCW雷达系统(从波形生成到利用小胞平均常误报率CA-CFAR进行目标检测)【含Matlab源码 15242期】含报告

&#x1f4a5;&#x1f4a5;&#x1f4a5;&#x1f4a5;&#x1f4a5;&#x1f4a5;&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;&#x1f49e;&#x1f49e;&#x1f49e;&#x1f49e;&#x1f49e;&#x1f49e;&#x1f49e;Matlab武动乾坤博客之家&#x1f49e;…...

忍者像素绘卷效果对比:亮色像素美学 vs 传统暗调像素艺术表现力

忍者像素绘卷效果对比&#xff1a;亮色像素美学 vs 传统暗调像素艺术表现力 1. 作品概述 忍者像素绘卷是一款基于Z-Image-Turbo深度优化的图像生成工作站&#xff0c;它将忍者文化与16-Bit复古游戏美学完美融合。这款工具最显著的特点是采用了全新的"亮色像素"界面…...

C语言基础:LiuJuan20260223Zimage嵌入式开发入门

C语言基础&#xff1a;LiuJuan20260223Zimage嵌入式开发入门 1. 学习目标与前置知识 如果你是刚开始接触嵌入式开发的C语言初学者&#xff0c;这篇文章就是为你准备的。我们将从最基础的C语言语法开始&#xff0c;一步步带你了解如何在嵌入式环境中使用C语言进行开发。不需要…...

新手入门指南:基于快马生成的代码理解设备配对功能实现

今天想和大家分享一个特别适合新手学习的设备配对功能实现案例。这个例子用最基础的HTML、CSS和原生JavaScript就能完成&#xff0c;特别适合刚接触前端开发的朋友理解交互逻辑。 项目结构设计 整个项目分为三个部分&#xff1a;两个模拟设备&#xff08;用不同图标表示&#x…...

PyTorch 2.8镜像真实效果:物理实验→电磁场/流体力学可视化视频

PyTorch 2.8镜像真实效果&#xff1a;物理实验→电磁场/流体力学可视化视频 1. 开箱即用的专业级物理模拟环境 当你第一次启动这个基于RTX 4090D优化的PyTorch 2.8镜像时&#xff0c;最直接的感受就是"专业工具就该这样"。这个镜像不是普通的深度学习环境&#xff…...

开发笔记:VSCode + Qt + clangd 明明能正常运行却满屏红波浪线

目录 开发笔记&#xff1a;VSCode Qt clangd 明明能正常运行却满屏红波浪线 前言 一、问题现象 二、根本原因&#xff1a;两套工具互不沟通 三、完整解决方案 方案 1&#xff1a;配置 .clangd&#xff08;最推荐、最根治&#xff09; 方案 2&#xff1a;自动生成 comp…...

群晖更换RAID类型无需重建服务,保持Volume磁盘盘符不变

我的环境&#xff1a;DSM型号&#xff1a;DS3617xs&#xff08;黑群晖&#xff09;系统版本&#xff1a;DSM 7.1.1-42962 Update 6硬盘数据库更新时间&#xff1a;2026-01-23更改前磁盘序号&#xff08;btrfs&#xff09;&#xff1a;Raid1&#xff08;volume1&#xff09;&…...

MySQL

我目前正在学习SQL语句,我所了解到的MySQL其实是一堆服务器,在下载服务器的时候,可以选择下载一些客户端,MySQL会自带一些客户端,像类似于终端的小黑框,还有什么bench;我还是喜欢外观好看的客户端 !我学SQL语句目前学到了数据类型,有数值型的,字符型的,二进制型的,值得一提的是…...