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

每日一题(8) 求解矩阵最小路径和问题

给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。

输入格式:

首先输入行数m及列数n,接下来输入m行,每行n个数。

输出格式:

输出第一行为最小路径(假定测试数据中的最小路径唯一),第2行为最小路径和。

输入样例1:

4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

输出样例1:

1 3 1 0 6 1 0 
12

问题分析

这是一个典型的路径规划问题,可以使用动态规划来解决。我们需要找到从矩阵左上角到右下角的最小路径和,并记录下这条路径。

在每个点上,我们只能向右或向下移动,因此到达位置 (i, j) 的路径只能来自于位置 (i-1, j)(上方)或位置 (i, j-1)(左方)。我们选择这两个来源中路径和较小的那个,然后加上当前位置的值,即可得到到达 (i, j) 的最小路径和。

解题思路

动态规划解法

我们定义:

  • dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的最小路径和
  • pace[i][j] 用于记录到达位置 (i, j) 的前一步是从哪个方向来的(0表示从上方,1表示从左方)

状态转移方程为:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j]

边界条件:

  • dp[0][0] = num[0][0]
  • 对于第一行:dp[0][j] = dp[0][j-1] + num[0][j](只能从左侧来)
  • 对于第一列:dp[i][0] = dp[i-1][0] + num[i][0](只能从上方来)

计算完 dp 数组后,dp[m-1][n-1] 就是我们要求的最小路径和。

为了重建最小路径,我们使用 pace 数组记录每一步的选择,然后用栈存储从终点回溯到起点的路径,最后输出即可得到完整路径。

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {public static void main(String[] args) throws IOException {BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(bf.readLine());int m = Integer.parseInt(st.nextToken());int n = Integer.parseInt(st.nextToken());int[][] num = new int[m][n];for(int i=0;i<m;i++){st = new StringTokenizer(bf.readLine());for(int j=0;j<n;j++){num[i][j] = Integer.parseInt(st.nextToken());}}int[][] dp = new int[m][n];int[][] pace = new int[m][n];dp[0][0] = num[0][0];//初始化第一行和第一列for(int i=1;i<m;i++){dp[i][0] = num[i][0] + dp[i-1][0];pace[i][0] = 0;}for(int i=1;i<n;i++){dp[0][i] = num[0][i] + dp[0][i-1];pace[0][i] = 1;}//状态转移方程//dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j];for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(dp[i-1][j]<dp[i][j-1]){dp[i][j] = dp[i-1][j] + num[i][j];pace[i][j] = 0;}else{dp[i][j] = dp[i][j-1] + num[i][j];pace[i][j] = 1;}}}//逆推路径Stack<Integer> temp = new Stack<>();int i=m-1,j=n-1;while (i>0||j>0){temp.push(num[i][j]);if(pace[i][j]==0) i--;else j--;}temp.push(num[0][0]);while (!temp.isEmpty()){System.out.print(temp.pop()+" ");}System.out.println();System.out.println(dp[m-1][n-1]);}
}

这种方法的时间复杂度为 O(m×n),空间复杂度也为 O(m×n),其中 m 和 n 分别是矩阵的行数和列数。 

相关文章:

每日一题(8) 求解矩阵最小路径和问题

给定一个m行n列的矩阵&#xff0c;从左上角开始每次只能向右或者向下移动&#xff0c;最后到达右下角的位置&#xff0c;路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。 输入格式: 首先输入行数m及列数n&#xff0c;接下来输入m行&#xff0c;每…...

JAVA设计模式:注解+模板+接口

1.基础组件 1.1注解类控制代码执行启动、停止、顺序 /*** author : test* description : 数据同步注解* date : 2025/4/18*/ Target({ElementType.TYPE}) Retention(RetentionPolicy.RUNTIME) Documented public interface SyncMeta {/*** 执行服务名称* return*/String name…...

如何在Linux系统中部署C++ Web应用

在 Linux 上部署 C Web 应用&#xff0c;和部署传统的 PHP 或 Node.js 应用相比更“原生”一些&#xff0c;通常涉及到自己编译、配置 Web 服务、处理依赖等。本文将详细讲解部署一个基于 C 编写的 Web 应用的完整流程&#xff0c;涵盖从构建、部署、到上线的每一步&#xff0c…...

实用工具-screenrec介绍(截图工具)

官方地址&#xff1a;Communicate Faster with Instant Video Messages & Screenshots 官方下载安装包&#xff0c;安装完成后&#xff0c;默认快捷键 alt s 开启截图&#xff0c;录屏 介绍 ScreenRec 是一款免费无广告的屏幕录制与截图工具&#xff0c;支持多平台&…...

使用veaury,在vue项目中运行react组件

网上的信息太少了&#xff0c;记录一下 我的项目是vue3webpack 使用&#xff1a;veaury Veaury 是基于React和Vue3的工具库&#xff0c;主要用于React和Vue在一个项目中公共使用的场景&#xff0c;主要运用在项目迁移、技术栈融合的开发模式、跨技术栈使用第三方组件的场景。 参…...

开源 vs. 闭源:大模型的未来竞争格局

开源 vs. 闭源&#xff1a;大模型的未来竞争格局 引言 在人工智能领域&#xff0c;尤其是大型语言模型(LLM)的发展中&#xff0c;开源与闭源之争已成为决定行业未来走向的关键议题。随着ChatGPT的横空出世和开源模型的蓬勃发展&#xff0c;技术社区正经历着一场深刻的范式转变…...

pcl代码解析

一、库基础代码解析&#xff1a; PCL库基础&#xff1a;点云类型与算法详解-CSDN博客 主要介绍PCL库的一些基本的点云类型、相关数据类型以及ROS接口消息&#xff0c;和一些常用的算法。 用到的一些PCL点云类型 pcl::PointXYZ: 这是最简单也可能是最常用到的点类型;它只储存…...

中华传承-医山命相卜-梅花易数

梅花易数 灵活起卦&#xff08;如数字、声音、外应等&#xff09;和象数结合&#xff0c;准确率可达96.8%。其起卦方式摆脱传统龟壳、蓍草的繁琐&#xff0c;强调直觉与灵活性。 个人决策、事件预测等 尤其在短期、具体问题上表现突出。...

HOOPS Exchange 与HOOPS Communicator集成:打造工业3D可视化新标杆!

一、概述 在工业3D开发、BIM建筑、数字孪生和仿真分析等高端应用场景中&#xff0c;数据格式复杂、模型体量庞大、实时交互体验要求高&#xff0c;一直是困扰开发者的难题。Tech Soft 3D旗下的HOOPS Exchange和HOOPS Communicator&#xff0c;正是解决这类问题的黄金搭档。二者…...

SQL预编译——预编译真的能完美防御SQL注入吗

SQL注入原理 sql注入是指攻击者拼接恶意SQL语句到接受外部参数的动态SQL查询中&#xff0c;程序本身 未对插入的SQL语句进行过滤&#xff0c;导致SQL语句直接被服务端执行。 拼接的SQL查询例如&#xff0c;通过在id变量后插入or 11这样的条件&#xff0c;来绕过身份验证&#…...

通过 Zotero 的样式编辑器(Style Editor)自定义文献引用和参考文献列表的格式

好的&#xff01;以下是一个更为详细的教程&#xff0c;帮助你通过 Zotero 的样式编辑器&#xff08;Style Editor&#xff09;自定义文献引用和参考文献列表的格式。 详细教程&#xff1a;使用 Zotero 样式编辑器自定义文献格式 1. 准备工作 在开始之前&#xff0c;请确保&a…...

PostgreSQL 通过 copy 命令导入几何数据 及 通过 CopyManager.copyIn() 导入几何数据

COPY命令介绍 copy是postgresql提供的一个专门用于快速导入导出数据的命令,通常用于从文件(TXT、CSV等)或标准输入输出中读取或写入数据。适合批量导入导出数据,速度快。 默认情况下,如果在处理过程中遇到错误,COPY将失败。 COPY只能用于表,不能用于视图!!! COPY…...

Next.js 技术详解:构建现代化 Web 应用的全栈框架

1. Next.js 概述 Next.js 是一个基于 React 的全栈框架&#xff0c;由 Vercel 团队开发和维护。它提供了一系列开箱即用的功能&#xff0c;使开发者能够快速构建高性能的 Web 应用。 核心优势 服务端渲染 (SSR)静态站点生成 (SSG)增量静态再生成 (ISR)文件系统路由API 路由图…...

【unity实战】Unity动画层级(Animation Layer)的Sync同步和Timing定时参数使用介绍,同步动画层制作角色的受伤状态

文章目录 前言方案一&#xff1a;复制粘贴原有层级的状态机1、实现2、问题 方法二&#xff1a;勾选Sync同步动画层1、简单实现同步2、同步blend tree的问题3、动画状态的播放时长4、下层状态覆盖了上层状态 专栏推荐完结 前言 如何制作角色的受伤状态&#xff1f; 玩家角色在…...

NFC 碰一碰发视频源码搭建,碰一碰发视频定制化开发技术

在移动互联时代&#xff0c;便捷的数据传输方式备受青睐。NFC&#xff08;近场通信&#xff09;技术以其操作简单、连接迅速的特性&#xff0c;为设备间的数据交互提供了高效解决方案。通过搭建 NFC 碰一碰发视频功能&#xff0c;用户只需将支持 NFC 的设备轻轻靠近&#xff0c…...

获取视频封面

目录 实现方式注意事项代码实现 实现方式 通过 video 元素canvas 元素的方式实现 生成 video 和 canvas 元素当 video 元素资源加载完成时&#xff0c;将 video 元素绘制到 canvas 画布上&#xff0c;然后通过 toBlob 或则 toDataURL 获取到对应的封面图片资源 注意事项 vid…...

c#开发大冲锋游戏登录器

1 前言 本文主要分享登录器的简要开发过程&#xff0c;只适合小白选手&#xff0c;高手请自动避让。 此项目是复刻大冲锋计划中的子集。 &#xff08;注&#xff1a;大冲锋是迅雷代理的一款次时代多职业第一人称FPS射击游戏&#xff0c;目前已经关服嗝屁。&#xff09; 2 …...

堆的实现以及利用堆进行排序

堆 堆的实现1. 什么是堆&#xff1f;2. 最小堆的核心操作2.1 初始化堆2.2 销毁堆2.3 插入元素2.4 删除堆顶元素2.5 获取堆顶元素2.6 判断堆是否为空 3. 调整堆的算法3.1 向上调整3.2 向下调整 4. 测试代码 堆排序一.向下调整建堆二.向上调整建堆 时间复杂度分析向上建堆分析&am…...

FPGA-VGA

目录 前言 一、VGA是什么&#xff1f; 二、物理接口 三、VGA显示原理 四、VGA时序标准 五、VGA显示参数 六、模块设计 七、波形图设计 八、彩条波形数据 前言 VGA的FPGA驱动 一、VGA是什么&#xff1f; VGA&#xff08;Video Graphics Array&#xff09;是IBM于1987年推出的…...

仿腾讯会议项目开发——界面关闭功能实现

目录 1、include(./netapi/netapi.pri) 2、加快构建速度 3、INCLUDEPATH./netapi 4、添加控制类 5、用单例模式创建一个Ckernel的对象 6、创建一个回收的槽函数 7、添加界面文件 8、创建一个私有的界面对象 9、修改为使用单例模式的控制类创建界面 10、在Ckernel类中…...

微信小程序怎么分包步骤(包括怎么主包跳转到分包)

第一步 主包跳转到分包 第一步 第二步...

点云配准控制迭代停止的阈值

在点云配准&#xff08;如ICP算法&#xff09;中&#xff0c;setEuclideanFitnessEpsilon() 是一个设置收敛条件的函数&#xff0c;用于控制迭代停止的阈值。以下是关于该参数的详细说明&#xff1a; 函数作用 setEuclideanFitnessEpsilon() 设置的是 两次连续迭代之间均方误…...

高频面试题:Android MVP/MVVM/MVI这几种架构在实际生产中,各自的优缺点和适用场景是什么

安卓开发早期的架构模式相对简单&#xff0c;许多开发者直接在Activity或Fragment中堆砌业务逻辑和UI操作&#xff0c;这种方式虽然在小型项目中看似高效&#xff0c;但随着代码量的增加&#xff0c;很快就会导致逻辑混乱、难以测试和维护的问题。Activity和Fragment作为安卓框…...

国内主要半导体厂家

以下是国内主要半导体厂家按产品类别&#xff08;模拟、数字、MCU、功率、传感器等&#xff09;的分类总结&#xff0c;涵盖各领域代表企业及其核心产品方向&#xff1a; ​一、模拟芯片&#xff08;Analog IC&#xff09;​​ ​圣邦微电子&#xff08;SGMICRO&#xff09;​​…...

DeepSeek深度观察:白宫“炒人“威胁的语义强度与市场应激量化分析

一、AI观察&#xff1a;政治博弈的语义强度分析 通过NLP情感分析模型对特朗普近期公开言论的语义解析显示&#xff0c;总统在社交媒体及记者会中多次使用"立即解雇""卷铺盖走人"等极端表述&#xff0c;其公开威胁解雇鲍威尔的推文互动量突破120万次&#…...

城市街拍暗色电影胶片风格Lr调色教程,手机滤镜PS+Lightroom预设下载!

调色介绍 城市街拍暗色电影胶片风格 Lr 调色&#xff0c;是借助 Adobe Lightroom 软件&#xff0c;为城市街拍的人像或场景照片赋予独特视觉风格的后期处理方式。旨在模拟电影胶片质感&#xff0c;营造出充满故事感与艺术感的暗色氛围&#xff0c;让照片仿佛截取于某部充满张力…...

图像分类标注小工具

图像分类标注小工具 不说废话 上代码 import os import cv2 import shutil import csvclass ImageLabeler:def __init__(self, input_dir, output_dir, class_names, csv_pathlabel_log.csv, preview_size(800, 800)):self.input_dir input_dirself.output_dir output_dirse…...

leetcode 2364. 统计坏数对的数目 中等

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i ! nums[j] - nums[i] &#xff0c;那么我们称 (i, j) 是一个 坏数对 。 请你返回 nums 中 坏数对 的总数目。 示例 1&#xff1a; 输入&#xff1a;nums [4,1,3,3] 输出&#xff1a;5 解释&#xff1a;数对…...

网络互连与互联网3

1.SMTP简单邮件传输协议&#xff0c;用于发送电子邮件&#xff0c;默认情况下是明文传输&#xff0c;没有加密机制。 SSL是一种安全协议&#xff0c;对电子邮件进行加密传输。 POP3主要用于接收电子邮件 IMAP用于接收电子邮件 2.采用存储-转发方式处理信号的设备是交换机 …...

docker部署springboot(eureka server)项目

打jar包 使用maven&#xff1a; <build><plugins><plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-compiler-plugin</artifactId><configuration><source>17</source><target>17&…...

git 出现 port 443 Connection timed out

梯子正常延迟不算严重&#xff0c;但在使用git push时反复出现 fatal: unable to access https://github.com/irvingwu5/xxxx.git/ Error in the HTTP2 framing layer Failed to connect to github.com port 443 after 136353 ms: Connection timed out 将git的网络配置与梯子…...

深入 MySQL 高级查询:JOIN、子查询与窗口函数的实用指南

在数据管理和分析的过程中&#xff0c;MySQL 提供了强大的查询功能&#xff0c;特别是在处理复杂数据关系时。本文将深入探讨 MySQL 的三种高级查询技术&#xff1a;JOIN、子查询和窗口函数。通过对这些技术的详细讲解和示例&#xff0c;帮助您更好地掌握并应用这些查询技巧。 …...

AXOP36061S: 60V 高压单通道运算放大器

AXOP36061S 是一款通用型高压带关断功能的单通道运算放大器&#xff0c;工作电压为3V至60V&#xff0c;具有17MHz的带宽和 15V/μs的压摆率&#xff0c;静态电流2.2mA&#xff0c;关断电流80μA&#xff0c;高耐压和宽带宽使其可以胜任绝大多数的高压应用场景。得益于对噪声和T…...

Aladdin显卡多任务运行教程

Aladdin显卡多任务运行 任务场景操作步骤其他说明 任务场景 当我运行我的代码后发现80G的显存仅占用了46G左右&#xff0c;还有很大空间没有被使用&#xff0c;于是想着能不能把剩下的空间也利用起来&#xff0c;于是有了接下来的工作。 操作步骤 当我们使用GPU run/debug/…...

Oracle AWR快照保留策略及其修改

文章目录 一、AWR快照保留机制及其修改方法二、生产环境建议三、监控建议 一、AWR快照保留机制及其修改方法 默认保留策略&#xff1a; • 标准保留期&#xff1a;8天 • 快照间隔&#xff1a;每小时1次&#xff08;默认&#xff09; • 存储位置&#xff1a;SYSAUX表空间 保留…...

日本公司如何实现B2B商城订货系统的自动化和个性化?

在日本构建具备前后台日文本地化、业务员代客下单、一客一价、智能拆单发货的B2B电商系统&#xff0c;需结合日本商业习惯与技术实现。以下是关键模块的落地方案&#xff1a; 一、系统架构设计 1. 前端本地化 语言与UI适配 采用全日语界面&#xff0c;包含敬语体系&#xff08…...

JavaScript 核心特性完全指南

引言 JavaScript 已经不再只是浏览器中的脚本语言,它支撑着前端、后端(Node.js)、桌面(Electron)、移动端(React Native)等多种生态。要在现代 Web 开发中游刃有余,除了会写代码,更要深刻理解语言特性、掌握常见模式和优化技巧。下面逐一深入解析 20 大核心特性。 1.…...

CentOS系统中排查进程异常终止的日志

在CentOS系统中排查进程异常终止的日志&#xff0c;可通过以下步骤结合多类日志文件和工具进行综合分析&#xff1a; 一、核心日志文件排查 系统全局日志‌ 查看 /var/log/messages&#xff1a;记录系统级错误、内核消息及进程异常终止信息&#xff0c;如OOM Killer事件‌。…...

Vue组件安全工程的量子跃迁:从基因改造到生态免疫

总章数字生命的进化论 2023年某电商平台红蓝对抗中&#xff0c;一个未净化的v-html指令导致千万用户数据泄露。当我们剖开现代Web应用的器官式架构&#xff0c;发现90%的安全漏洞都源自组件间的信任危机。本文将带您见证如何用军工级防御体系重构Vue组件&#xff0c;使其具备类…...

编程技能:调试03,逐过程命令与退出调试

专栏导航 本节文章分别属于《Win32 学习笔记》和《MFC 学习笔记》两个专栏&#xff0c;故划分为两个专栏导航。读者可以自行选择前往哪个专栏。 &#xff08;一&#xff09;WIn32 专栏导航 上一篇&#xff1a;编程技能&#xff1a;调试02&#xff0c;设置断点与删除断点 回…...

基于Ubuntu22.04和OpenCV4.5.4的物联网人脸识别考勤机

前言&#xff1a;本人已有Ubuntu22.04的相关开发环境配置&#xff0c;并且默认C和机器学习基础&#xff0c;这里直接从安装opencv开始&#xff0c;完整代码在最后。具体情况具体分析&#xff0c;请以实际为主。 视频参考&#xff1a;【大厂敲门砖】从0到1做一个物联网人脸识别…...

java 排序算法-快速排序

快速排序&#xff08;Quick Sort&#xff09;是一种高效的排序算法&#xff0c;它使用分治法&#xff08;Divide and Conquer&#xff09;策略来把一个序列分为较小和较大的两个子序列&#xff0c;然后递归地排序两个子序列。 快速排序算法的基本思想&#xff1a; 选择基准值&…...

openEuler系统下源码编译安装Nginx实践教程

openEuler 24.03 LTS 源码编译安装Nginx实践教程 前言一、环境准备1. 系统要求2. 更新系统与基础配置二、依赖安装1. 安装编译工具链2. 安装Nginx核心依赖三、源码编译安装1. 下载Nginx源码2. 创建专用系统用户3. 配置编译参数4. 编译与安装四、服务配置与管理1. 创建Systemd服…...

helloword 1(安卓逆向工具简单利用)

题目 做法 下载&#xff0c;不要解压&#xff0c;直接拖入Exeinfo PE进行分析 文件后缀是apk&#xff0c;判断为安卓逆向题 拖进ApkIDE 先找主函数main函数&#xff0c;这题的flag直接出来了 &#xff08;搜索内容不要习惯性空格之类&#xff0c;这样会找不出来&#xff09;…...

基于ONT数据的乳腺癌BRCA1和BRCA2变异检测方法

评估 BRCA1/2 分子状态已成为乳腺癌患者治疗的标准操作。例如聚合酶抑制剂(PARPi)的开发和临床应用,PARPi 是肿瘤学家新疗法中的关键方式。已发现 PARPi 可改善携带 BRCA1/2 种系或体细胞突变的乳腺癌患者的临床结局,提高患者生存率和生活质量。因此,目前全球指南强烈建议…...

uniapp运行在app端如何使用缓存

uniapp运行在app端如何使用缓存 ​ 众所周知&#xff0c;uniapp可以一套代码&#xff0c;多端运行。但是需要注意的是&#xff0c;window对象以及document是浏览器特有的(所以app端无法使用localStorage等api)&#xff0c;因此&#xff0c;uniapp贴心的为我们准备了getStorage…...

人工智能代理重塑数字成功:为何面向机器的营销是下一前沿

随着人工智能&#xff08;AI&#xff09;改变消费者与数字世界的互动方式&#xff0c;数字营销正迎来一场革命性变革。2025年4月14日发布的一项研究揭示了AI代理——代表用户自主研究、比较和推荐产品或服务的系统——的日益增长的影响力。该研究探讨了这些代理如何与在线内容交…...

《奇迹世界起源》:神之月晓活动介绍!

神之月晓是《奇迹世界起源》手游中的一项限时抽奖活动&#xff0c;为玩家提供了获取丰厚奖励的机会。活动期间&#xff0c;玩家可以通过充值达到指定金额获得抽奖资格&#xff0c;每次充值一定金额即可获得一次抽奖机会&#xff0c;每天有抽奖次数上限。 活动规则&#xff1a;…...

AI测试用例生成平台

AI测试用例生成平台 项目背景技术栈业务描述项目展示项目重难点 项目背景 针对传统接口测试用例设计高度依赖人工经验、重复工作量大、覆盖场景有限等行业痛点&#xff0c;基于大语言模型技术实现接口测试用例智能生成系统。 技术栈 LangChain框架GLM-4模型Prompt Engineeri…...

【web服务_负载均衡Nginx】二、Nginx 核心技术之负载均衡与反向代理

一、负载均衡与反向代理概述​ 在互联网应用场景中&#xff0c;随着用户访问量的不断增加&#xff0c;单台服务器往往难以满足性能和可靠性的需求。负载均衡与反向代理技术应运而生&#xff0c;成为保障高并发、稳定服务的关键技术。负载均衡旨在将大量的客户端请求合理分配到…...