算法每日一练 (9)
💢欢迎来到张胤尘的技术站
💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥
文章目录
- 算法每日一练 (9)
- 最小路径和
- 题目描述
- 解题思路
- 解题代码
- `c/c++`
- `golang`
- `lua`
官方站点: 力扣 Leetcode
算法每日一练 (9)
最小路径和
题目地址:最小路径和
题目描述
给定一个包含非负整数的 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] <= 200
解题思路
-
首先根据题目要求判断边界条件,当
m == n == 1
时,不需要任何处理,直接返回即可。 -
由题意可知,在矩阵中任何一个节点只有一种方式可到达:从左边或上边,那么假设
i
是矩阵的横坐标,j
是矩阵的纵坐标,则有如下规则:- 当
i == 0
并且j == 0
时,就是(0,0)
点,到达当前位置的路径最小和满足如下公式:
t m p [ i ] [ j ] = g r i d [ i ] [ j ] tmp[i][j] = grid[i][j] tmp[i][j]=grid[i][j] - 当
i == 0
时,只能从左边到达,到达当前位置的路径最小和满足如下公式:
t m p [ i ] [ j ] = g r i d [ i ] [ j ] + t m p [ i ] [ j − 1 ] tmp[i][j] = grid[i][j] + tmp[i][j-1] tmp[i][j]=grid[i][j]+tmp[i][j−1] - 当
j == 0
时, 只能从上面到达,到达当前位置的路径最小和满足如下公式:
t m p [ i ] [ j ] = g r i d [ i ] [ j ] + t m p [ i − 1 ] [ j ] tmp[i][j] = grid[i][j] + tmp[i-1][j] tmp[i][j]=grid[i][j]+tmp[i−1][j] - 当
i != 0
并且j != 0
时,到达当前位置的路径最小和满足如下公式:
t m p [ i ] [ j ] = g r i d [ i ] [ j ] + m i n ( t m p [ i − 1 ] [ j ] , t m p [ i ] [ j − 1 ] ) tmp[i][j] = grid[i][j] + min(tmp[i-1][j], tmp[i][j-1]) tmp[i][j]=grid[i][j]+min(tmp[i−1][j],tmp[i][j−1])
- 当
-
创建临时矩阵
tmp
,根据以上的公式依次给矩阵中的每个元素赋值。 -
返回
tmp[m-1][n-1]
的值,因为tmp[m-1][n-1]
存储的是就是到达右下角的最小路径和。
golang
的解法采用了上述的解题思路;c/c++
和lua
的解法采用了一维数组作为临时容器,感兴趣的同学可以作为参考。
解题代码
c/c++
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();if (m == 1 && n == 1)return grid[0][0];std::vector<int> tmp;tmp.resize(n);for (int j = 0; j < n; j++) {if (j == 0)tmp[j] = grid[0][j];elsetmp[j] = grid[0][j] + tmp[j - 1];}for (int i = 1; i < m; i++) {for (int j = 0; j < n; j++) {if (j == 0)tmp[j] += grid[i][j];elsetmp[j] = grid[i][j] + std::min(tmp[j - 1], tmp[j]);}}return tmp[n - 1];}
};
golang
func minPathSum(grid [][]int) int {m := len(grid)n := len(grid[0])if m == 1 && n == 1 {return grid[0][0]}tmp := make([][]int, m)for i := 0; i < m; i++ {tmp[i] = make([]int, n)for j := 0; j < n; j++ {if i == 0 && j == 0 {tmp[i][j] = grid[i][j]} else if i == 0 {tmp[i][j] = grid[i][j] + tmp[i][j-1]} else if j == 0 {tmp[i][j] = grid[i][j] + tmp[i-1][j]} else {tmp[i][j] = grid[i][j] + min(tmp[i-1][j], tmp[i][j-1])}}}return tmp[m-1][n-1]
}
lua
local function minPathSum(grid)local m, n = #grid, #grid[1]if m == 1 and n == 1 thenreturn grid[1][1]endlocal tmp = {}for j = 1, n doif j == 1 thentmp[j] = grid[1][j]elsetmp[j] = grid[1][j] + tmp[j - 1]endendfor i = 2, m dofor j = 1, n doif j == 1 thentmp[j] = tmp[j] + grid[i][j]elsetmp[j] = grid[i][j] + math.min(tmp[j], tmp[j - 1])endendendreturn tmp[n]
end
🌺🌺🌺撒花!
如果本文对你有帮助,就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容,请随时向我提问。
相关文章:

算法每日一练 (9)
💢欢迎来到张胤尘的技术站 💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥 文章目录 算法每日一练 (9)最小路径和题目描述解题思路解题代码…...
软考高级信息系统项目管理师笔记-第10章项目进度管理
第10章项目进度管理 10.1 管理基础 10.1.1 项目进度计划的定义和总要求 1、项目进度计划是 一种用于沟通和管理干系人期望的工具,为绩效报告提供依据。 2、项目管理团队编制进度计划的一般步骤为: 首先选择进度计划方法,例如关键路径法; 然后将项目特定数据,如活动、计…...
专门为高速连续扫描设计的TDI工业相机
TDI(Time Delay Integration,时间延迟积分)工业相机是一种基于特殊CCD(电荷耦合器件)技术的成像设备,主要用于高速、高灵敏度、高分辨率的图像采集场景。其核心原理是通过多级积分和同步电荷转移技术&#…...

【Vue3】实现一个超过高度后可控制显示隐藏的组件
组件效果图 未达到最大高度 达到设置的最大高度 进行展开 实现代码 组件代码 备注:通过tailwindcss设置的样式,通过element-plus/icons-vue设置的图标,可根据情况进行替换 <template><!-- 限制高度组件 --><div ref"…...
Spring提供的SPEL表达式
SPEL 1. 概述 SpEL是Spring框架中用于表达式语言的一种方式。它类似于其他编程语言中的表达式语言,用于在运行时计算值或执行特定任务。 SpEL提供了一种简单且强大的方式来访问和操作对象的属性、调用对象的方法,以及实现运算、条件判断等操作。它可以…...

JAVA编程【jvm垃圾回收的差异】
jvm垃圾回收的差异 JVM(Java Virtual Machine)的垃圾回收(GC)机制是自动管理内存的一种方式,能够帮助开发者释放不再使用的内存,避免内存泄漏和溢出等问题。不同的垃圾回收器(GC)有…...

Elasticsearch:“Your trial license is expired”
目录标题 问题原因解决方案 问题 原因 ES的X-pack许可证是提供免费一个月的试用,到期之后就会报这个错误。 解决方案 查看license GET _license 开启试用license POST _xpack/license/start_trial?acknowledgetrue修改为基础license POST _xpack/license/start_…...

fmql之Linux WDT
正点原子第52章。 基础知识 正点原子教程 fmql-dts 代码 APP代码(不需要编写驱动代码) static int dw_wdt_drv_probe(struct platform_device *pdev) {struct device *dev &pdev->dev;struct watchdog_device *wdd;struct dw_wdt *dw_wdt; …...

【算法学习之路】7.链表算法
链表算法 前言一.原地逆置思路一:头插法思路二:双指针法思路3:递归 例题:1.头插法2.双指针法3,递归 二.双指针快慢指针:一个指针快一个指针慢例题1例题2 前言 我会将一些常用的算法以及对应的题单给写完&am…...

IDEA Commit 模态提交界面关闭VS开启对比
IDEA Commit 模态提交界面关闭VS开启对比 前言开启模态提交界面优点快捷且灵活的选择需要commit文件显示文件修改内容多(主观) 缺点在模态提交界面选择文件,临时关闭模态框重新打开会重置选择的commit文件 关闭模态提交界面优点允许在commit选择文件时查看其它没有修…...
【AI赋能】AI 工具生成视频教材:从创意到成品的全流程指南
AI 工具生成视频教材:从创意到成品的全流程指南 目标 通过本教材,您将学会如何利用 AI 工具(Grok、Sora、Speechify 和 CapCut)生成一个完整的视频,包括脚本生成、视频片段制作、字幕添加、音频生成以及最终剪辑合成…...
qt 操作多个sqlite文件
qt 操作多个sqlite文件 Chapter1 qt 操作多个sqlite文件1. 引入必要的头文件2. 创建并连接多个SQLite数据库3. 代码说明4. 注意事项 Chapter2 qt 多线程操作sqlite多文件1. 引入必要的头文件2. 创建数据库操作的工作线程类3. 在主线程中创建并启动多个工作线程4. 代码说明5. 运…...

WSL with NVIDIA Container Toolkit
一、wsl 下安装 docker 会提示安装 docekr 桌面版,所以直接安装 docker 桌面版本即可 二、安装 NVIDIA Container Toolkit NVIDIA Container Toolkit仓库 https://github.com/NVIDIA/nvidia-container-toolkitgithub.com/NVIDIA/nvidia-container-toolkit 安装…...

Vue 系列之:组件通讯
子组件调用父组件方法 1、直接在子组件中通过 this.$parent.event 来调用父组件的方法 父组件: <template><p><child></child></p> </template> <script>import child from ./child;export default {components: {chi…...

【Linux实践系列】:用c语言实现一个shell外壳程序
🔥本文专栏:Linux Linux实践项目 🌸博主主页:努力努力再努力wz 那么今天我们就要进入Linux的实践环节,那么我们之前学习了进程控制相关的几个知识点,比如进程的终止以及进程的等待和进程的替换,…...
STL map 的 lower_bound(x)、upper_bound(x) 等常用函数
【STL map 简介】 ● STL map 是一种关联容器,存储键值对,每个键(key value)是唯一的,而值(mapped value)可以重复。构建 STL map 时,无论元素插入顺序如何,STL map 中的…...

【A2DP】SBC 编解码器互操作性要求详解
目录 一、SBC编解码器互操作性概述 二、编解码器特定信息元素(Codec Specific Information Elements) 2.1 采样频率(Sampling Frequency) 2.2 声道模式(Channel Mode) 2.3 块长度(Block Length) 2.4 子带数量(Subbands) 2.5 分配方法(Allocation Method) 2…...
Computational Linguistics期刊全解析:领域顶刊的投稿指南与学术价值
在人工智能与语言学交叉融合的浪潮中,《Computational Linguistics》(CL)作为该领域的标杆期刊,始终是研究者发表前沿成果的首选平台。本文将从期刊影响力、投稿策略、收稿方向等角度,为学者提供一份全面的指南。 一、…...
【量化科普】Sharpe Ratio,夏普比率
【量化科普】Sharpe Ratio,夏普比率 🚀量化软件开通 🚀量化实战教程 在量化投资领域,夏普比率(Sharpe Ratio)是一个非常重要的风险调整后收益指标。它由诺贝尔经济学奖得主威廉F夏普(William…...

运行OpenManus项目(使用Conda)
部署本项目需要具备一定的基础:Linux基础、需要安装好Anaconda/Miniforge(Python可以不装好,直接新建虚拟环境的时候装好即可),如果不装Anaconda或者Miniforge,只装过Python,需要确保Python是3.…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...