最小路径和[中等]
优质博文:IT-BLOG-CN
一、题目
给定一个包含非负整数的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
二、代码
动态规划
状态定义:设 dp 为大小 m×n 矩阵,其中 dp[i][j] 的值代表直到走到 (i,j) 的最小路径和。
转移方程:题目要求,只能向右或向下走,换句话说,当前单元格 (i,j) 只能从左方单元格 (i−1,j) 或上方单元格 (i,j−1) 走到,因此只需要考虑矩阵左边界和上边界。
走到当前单元格 (i,j) 的最小路径和 = “从左方单元格 (i−1,j) 与 从上方单元格 (i,j−1) 走来的 两个最小路径和中较小的 ” + 当前单元格值 grid[i][j] 。具体分为以下 4 种情况:
当左边和上边都不是矩阵边界时: 即当i!=0, j!=0时,dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j] ;
当只有左边是矩阵边界时: 只能从上面来,即当i=0,j!=0时, dp[i][j]=dp[i][j−1]+grid[i][j] ;
当只有上边是矩阵边界时: 只能从左面来,即当i!=0,j=0时, dp[i][j]=dp[i−1][j]+grid[i][j] ;
当左边和上边都是矩阵边界时: 即当i=0,j=0时,其实就是起点, dp[i][j]=grid[i][j];
初始状态:dp 初始化即可,不需要修改初始 0 值。
返回值:返回 dp 矩阵右下角值,即走到终点的最小路径和。
其实我们完全不需要建立 dp 矩阵浪费额外空间,直接遍历 grid[i][j] 修改即可。这是因为:grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ;原 grid 矩阵元素中被覆盖为 dp 元素后(都处于当前遍历点的左上方),不会再被使用到。
class Solution {public int minPathSum(int[][] grid) {for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(i == 0 && j == 0) continue;else if(i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];else if(j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];}}return grid[grid.length - 1][grid[0].length - 1];}
}
时间复杂度 O(M×N) 遍历整个grid矩阵元素。
空间复杂度 O(1) 直接修改原矩阵,不使用额外空间。
空间复杂度可以优化到原地工作,也就是O1,但是会破坏原矩阵的数据。通过分析可以发现,数据在扫描矩阵的时候,原数据信息只在扫描的时候用到一次,后续便不会再使用,所以扫描写dp的时候,可以直接进行覆盖,而不会影响最终的结局。也就是利用了系统为grid分配的内存进行记录动态规划的dp。下面贴上代码(代码写的烂,如果有人读到了,还请见谅)
#define min(x,y) ((x) > (y)) ? (y) : (x)int minPathSum(int** grid, int gridSize, int* gridColSize){unsigned char i,j;for(j = 1; j < *gridColSize;j++) grid[0][j] += grid[0][j-1];for(i = 1; i < gridSize;i++) grid[i][0] += grid[i-1][0];for(i = 1; i < gridSize; i++)for(j = 1; j < *gridColSize;j++ ) grid[i][j] += min(grid[i-1][j],grid[i][j-1]);return grid[gridSize-1][*gridColSize-1];
}
相关文章:
最小路径和[中等]
优质博文:IT-BLOG-CN 一、题目 给定一个包含非负整数的m x n网格grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 1: 输入:grid [[…...
【题库】——数组 小鱼比可爱
#include<bits/stdc.h> using namespace std; int main() {int n,m,i;cin>>n;int arr[n]; for(i0;i<n;i) {int count 0;cin>>arr[i];for(mi;m>0;m--){if(arr[i]>arr[m])count;} cout<<count<<" "; } return 0; }...
基于飞腾平台的Hbase的安装配置
【写在前面】 飞腾开发者平台是基于飞腾自身强大的技术基础和开放能力,聚合行业内优秀资源而打造的。该平台覆盖了操作系统、算法、数据库、安全、平台工具、虚拟化、存储、网络、固件等多个前沿技术领域,包含了应用使能套件、软件仓库、软件支持、软件适…...
【springboot】springboot接口参数全局解密,解决request内容修改后如何重新设置回去的问题
文章目录 核心思路spring&servelt基础核心接口类核心代码 body解密核心原理讲解get解密核心原理讲解get query请求讲解get pathVariables请求讲解 总结 本文不仅介绍了body内容修改后如何传递,也介绍了get请求 在修改内容后如何继续传递。 【原创作者 csdn: 孟秋…...
yml基本语法
YAML(YAML Ain’t Markup Language)是一种简洁且易读的数据序列化格式,常用于配置文件。Spring Boot 中的 application.yml 文件使用 YAML 来配置应用程序的属性。 YAML 基本语法 1. 键值对 基本的键值对表示形式为:key: value…...
橙色简洁大气体育直播自适应模板赛事直播门户自适应网站源码
源码名称:酷黑简洁大气体育直播自适应模板赛事直播门户网站 源码开发环境:帝国cms 7.5 安装环境:phpmysql 带采集,可以挂着电脑上自动采集发布,无需人工操作! 橙色简洁大气体育直播自适应模板赛事直播门户…...
【启明智显技术分享】工业级HMI芯片Model系列GUI合成到项目中的指南
在工业自动化、智能终端HMI、车载仪表盘等领域,高性能的HMI(人机界面)芯片是不可或缺的核心组件。启明智显推出的Model系列(如Model3C、Model3、Model4)HMI芯片,以其卓越的性能和广泛的应用领域,…...
开源服务器运维工具1Panel
1Panel是杭州飞致云信息科技有限公司推出的一款现代化、开源的Linux服务器运维管理面板。 以下是对1Panel的详细介绍: 一、基本信息 产品名称:1Panel所属公司:杭州飞致云信息科技有限公司编写语言:Golang上线时间:20…...
新版本源2.0大模型发布:Yuan2-2B-July-hf
引言 近日,浪潮信息的新一代基础语言大模型源2.0 迎来了重要更新。浪潮信息正式发布了 Yuan2-2B-July-hf 模型,标志着源2.0系列模型在性能和功能上的进一步提升。这一版本将为开发者和研究人员提供更强大的工具,以满足各种语言处理需求。…...
用python生成GIF动图—用于博客插图或封面等
生成GIF动图🚀 由于目前自己是在做大模型,还有一些树莓派硬件之类的东西,一是大模型的流式输出的例子需要用到GIF,二是做单片机的时候例如一些灯的闪烁和变化需要用到,所以之前也是一直有这个打算所以就记录一下这个生…...
[RCTF2019]draw
下载是一个文本文档,百度AI cs pu lt 90 fd 500 rt 90 pd fd 100 rt 90 repeat 18[fd 5 rt 10] lt 135 fd 50 lt 135 pu bk 100 pd setcolor pick [ red orange yellow green blue violet ] repeat 18[fd 5 rt 10] rt 90 fd 60 rt 90 bk 30 rt 90 fd 60 pu lt 90 f…...
设计模式 - 责任链模式
💝💝💝首先,欢迎各位来到我的博客!本文深入理解设计模式原理、应用技巧、强调实战操作,提供代码示例和解决方案,适合有一定编程基础并希望提升设计能力的开发者,帮助读者快速掌握并灵活运用设计模式。 💝💝💝如有需要请大家订阅我的专栏【设计模式】哟!我会定…...
jpg怎么转换成pdf?6个简单方法,实现jpg转换成pdf
你是否也曾想将jpg图片转换为pdf格式文档呢?亦或者在处理文档或制作报告时,不知道怎么才能更快地将多张图片整合成一个pdf文件呢?如果你正在寻找简单快速的方法,又有哪些工具可以帮助您完成图片转pdf呢?别着急…...
ptrade排坑笔记——使用量化交易的时候有报错提示!
前言 今天要和大家分享一个遇见的问题,有客户反馈,自己在使用量化交易的时候,会有报错!会在后文分享我们是如何解决这个问腿的! 一、问题描述 客户主要遇见的问题是,量化在进行交易的过程中,…...
C#-MemoryMarshal
MemoryMarshal 类是 .NET 中用于处理内存的工具类,它提供了一组静态方法,用于在托管代码中以安全和高效的方式操作内存块。MemoryMarshal 类主要用于处理原始内存数据而不需要进行复制,这对于性能关键的操作非常有用。 MemoryMarshal 类包含…...
Java并发编程的艺术
Java作为一门面向对象的编程语言,自1995年推出以来,一直以其稳定性、跨平台性和丰富的API受到广大开发者的喜爱。在Java的发展历程中,并发编程一直是其重要的特性之一。本文将探讨Java并发编程的艺术,解析其核心概念和常用并发工具…...
华为 OLT 添加 ONU 配置 (SNMP管理模式)
上网业务数据规划 OLT PON口 0/8/0 ONU_ID 0 ONU 序列号 4857544323BE233B 外层 VLAN ID 2012 内层VLAN ID 35 用户 FE 端口 ONU 0/1/1 用户VLAN 35 DBA带宽类型 Type 2 流量模板编号 10 DBA 模板编号 30 ONU线路模板编号 40 T-CONT (网管) 0 T-CONT(业务_ 2 GEM (网管) 0 …...
【JavaScript】[]和{} 的转换
背景 ([])? true:false ({})? true:false ([] true)? true:false ({} true)? true:false ([] true)? true:false ({} true)? true:false分析 [ ]和{ } 都是复杂类型,以上都是三目运算符判断 1.判断[ ]和{ } 是否存在 声明了这些已经分配了内存…...
C#关于多线程的线程问题
using System.Text; namespace 平时练习8._19day06 {internal class Program{static async Task Main(string[] args){Console.WriteLine(Thread.CurrentThread.ManagedThreadId );StringBuilder sb new StringBuilder();for (int i 0; i < 10000; i){sb.Append("…...
eclipse打开失败 java was started but returned exit code=13
报错详细信息如下 原因:eclipse版本和jdk版本不一致。系统之前jdk是1.6,然后安装1.8之后默认修改了环境变量。导致eclipse启动失败 解决方案:修改eclipse目录下的eclipse.ini文件增加一下内容。文档说明:eclipse.ini - Eclipsepe…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
VASP软件在第一性原理计算中的应用-测试GO
VASP软件在第一性原理计算中的应用 VASP是由维也纳大学Hafner小组开发的一款功能强大的第一性原理计算软件,广泛应用于材料科学、凝聚态物理、化学和纳米技术等领域。 VASP的核心功能与应用 1. 电子结构计算 VASP最突出的功能是进行高精度的电子结构计算ÿ…...
TI德州仪器TPS3103K33DBVR低功耗电压监控器IC电源管理芯片详细解析
1. 基本介绍 TPS3103K33DBVR 是 德州仪器(Texas Instruments, TI) 推出的一款 低功耗电压监控器(Supervisor IC),属于 电源管理芯片(PMIC) 类别,主要用于 系统复位和电压监测。 2. …...
C++ 变量和基本类型
1、变量的声明和定义 1.1、变量声明规定了变量的类型和名字。定义初次之外,还申请存储空间,也可能会为变量赋一个初始值。 如果想声明一个变量而非定义它,就在变量名前添加关键字extern,而且不要显式地初始化变量: e…...
