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

突破百度网盘限速瓶颈:BaiduPCS-Go命令行客户端完全指南

突破百度网盘限速瓶颈&#xff1a;BaiduPCS-Go命令行客户端完全指南 【免费下载链接】BaiduPCS-Go iikira/BaiduPCS-Go原版基础上集成了分享链接/秒传链接转存功能 项目地址: https://gitcode.com/GitHub_Trending/ba/BaiduPCS-Go 你是否厌倦了百度网盘那令人抓狂的下载…...

如何解决Tokio项目中Windows平台TCP性能问题的完整指南

如何解决Tokio项目中Windows平台TCP性能问题的完整指南 【免费下载链接】tokio A runtime for writing reliable asynchronous applications with Rust. Provides I/O, networking, scheduling, timers, ... 项目地址: https://gitcode.com/GitHub_Trending/to/tokio To…...

YOLO12应用场景:零售货架识别中商品计数+品类分类一体化方案

YOLO12应用场景&#xff1a;零售货架识别中商品计数品类分类一体化方案 1. 引言&#xff1a;零售货架管理的痛点与新解法 如果你经营过一家便利店、超市&#xff0c;或者负责过零售门店的运营&#xff0c;一定对“货架盘点”这件事深有感触。每到月底或者需要补货时&#xff…...

DeepSeek-Coder-V2终极指南:如何免费打造你的专属AI编程助手

DeepSeek-Coder-V2终极指南&#xff1a;如何免费打造你的专属AI编程助手 【免费下载链接】DeepSeek-Coder-V2 DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligence 项目地址: https://gitcode.com/GitHub_Trending/de/DeepSeek-Coder-V2 …...

Hunyuan-MT-7B多语种能力:Pixel Language Portal在联合国六种官方语言互译中的表现

Hunyuan-MT-7B多语种能力&#xff1a;Pixel Language Portal在联合国六种官方语言互译中的表现 1. 引言&#xff1a;当像素冒险遇见多语言翻译 在全球化交流日益频繁的今天&#xff0c;语言障碍仍然是横亘在不同文化之间的无形壁垒。传统翻译工具往往给人冰冷、机械的使用体验…...

python协同过滤算法的基于python二手物品交易网站系统

目录同行可拿货,招校园代理 ,本人源头供货商协同过滤算法在二手物品交易网站中的应用用户行为数据收集基于用户的协同过滤基于物品的协同过滤混合推荐策略冷启动问题处理实时推荐更新推荐结果评估代码实现示例系统功能整合性能优化项目技术支持源码获取详细视频演示 &#xff1…...

电子测试岗面试翻车实录:我的硬件知识与英语短板,以及如何逆袭”

一&#xff1a;首先进行英文的自我介绍Hello, my name isxxx .你好&#xff0c;我叫xxx。I’m 20 years old, and I’m currently a third-year student majoring inElectronic Information Engineering at xxxx我今年20岁&#xff0c;目前是xxx电子信息工程专业的大三学生。My…...

管理员命令提示符 命令提示符 cmd

命令提示符区别...

软考软件评测师备考避坑指南:过来人告诉你这5个章节最容易丢分(附2024最新考纲解析)

软考软件评测师备考避坑指南&#xff1a;5个高频失分章节深度解析 第一次打开软件评测师考纲时&#xff0c;我盯着密密麻麻的知识点列表发愣——这哪是考试大纲&#xff0c;分明是软件工程领域的百科全书。作为经历过三次备考最终以87分通过的老考生&#xff0c;我深刻理解那种…...

深度解析:数据仓库——定义、核心架构与企业核心价值

深度解析&#xff1a;数据仓库——定义、核心架构与企业核心价值一、引言二、定义&#xff1a;什么是数据仓库&#xff1f;2.1 标准定义2.2 核心四大特征&#xff08;数据仓库基石&#xff09;三、架构流程&#xff1a;数据仓库的标准工作流程&#xff08;带流程图&#xff09;…...