力扣hot100 最小路径和 多维DP 滚动数组 一题多解

Problem: 64. 最小路径和
在这里插入图片描述

文章目录

  • 思路
  • 💖 朴素版
  • 💖 空间优化版

思路

👨‍🏫 路飞

在这里插入图片描述

💖 朴素版

⏰ 时间复杂度: O ( n m ) O(nm) O(nm)
🌎 空间复杂度: O ( n m ) O(nm) O(nm)

class Solution {public int minPathSum(int[][] grid){int n = grid.length;if (n == 0)return 0;int m = grid[0].length;int[][] f = new int[n][m];f[0][0] = grid[0][0];for (int i = 1; i < m; i++)f[0][i] = f[0][i - 1] + grid[0][i];for (int i = 1; i < n; i++)f[i][0] = f[i - 1][0] + grid[i][0];for (int i = 1; i < n; i++)for (int j = 1; j < m; j++)f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];return f[n - 1][m - 1];}
}

💖 空间优化版

⏰ 时间复杂度: O ( n m ) O(nm) O(nm)
🌎 空间复杂度: O ( 1 ) O(1) O(1)

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];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/249118.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

查看Windows 所有账户方法

目标 了解Windows查看所有账户的方法 方法 方法1&#xff1a;本地和用户组 按下Win X键&#xff0c;选择“计算机管理”。在计算机管理界面的左侧面板中&#xff0c;展开“系统工具” -> “本地用户和组” -> “用户”。在右侧窗口中&#xff0c;查看列出的所有用户账…

数据结构+算法(第01篇):走下神坛吧!算法

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 学习必须往深处挖&…

科技云报道:新趋势下,国产数据库或“春山可望”

科技云报道原创。 从540亿元到1286亿元——这是中国通信标准化协会大数据技术标准推进委员会针对中国数据库行业给出的一份预测报告。 报告指出&#xff0c;未来五年&#xff0c;中国数据库行业将从百亿级市场跨越成为千亿级市场。 最近两年&#xff0c;中国的数据库行业似乎…

Docker核心教程

1. 概述 官网&#xff1a;https://docs.docker.com/ Docker Hub 网站&#xff1a;https://hub.docker.com/ 容器较为官方的解释&#xff1a; 一句话概括容器&#xff1a;容器就是将软件打包成标准化单元&#xff0c;以用于开发、交付和部署。 容器镜像是轻量的、可执行的独立…

leetcode—跳跃游戏—贪心算法

1 跳跃游戏1 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&a…

Codeforces Round 922 (Div. 2)补题

Brick Wall&#xff08;Problem - A - Codeforces&#xff09; 题目大意&#xff1a;规定砖的大小为1*k&#xff08;k>2&#xff09;,现在有一面n*m的砖墙&#xff0c;n是墙高&#xff0c;m是墙宽&#xff0c;砖在砖墙中有两种放法&#xff0c;水平放置和竖直放置&#xff…

注册亚马逊店铺用动态IP可以吗?

注册亚马逊店铺可以用动态IP&#xff0c;只要是独立且干净的网线就没问题&#xff0c;亚马逊规则要求一个IP地址只能出现一个亚马逊店铺&#xff0c;若使用不当会导致关联账户。 固定ip可以给我们的账户带来更多的安全&#xff0c;要知道关联问题是亚马逊上的一个大问题&#…

《动手学深度学习(PyTorch版)》笔记4.8

注&#xff1a;书中对代码的讲解并不详细&#xff0c;本文对很多细节做了详细注释。另外&#xff0c;书上的源代码是在Jupyter Notebook上运行的&#xff0c;较为分散&#xff0c;本文将代码集中起来&#xff0c;并加以完善&#xff0c;全部用vscode在python 3.9.18下测试通过。…

人工智能基础-Numpy.array基本操作

基本属性 查看维度 x.ndim查看维度&#xff08;元组形式&#xff09; x.shape元素个数 x.size数据访问 子矩阵 内容同步修改 加是copy&#xff08;&#xff09;则不同步修改 Reshape 修改维度 参数为-1时自动识别个数 合并 np.concatenate([x, y])沿着列合并 np.co…

第十四届蓝桥杯大赛软件赛省赛(C/C++ 大学B组)题解

尝试再做一次&#xff0c;我记得还是有点难&#xff0c;我会尽量多写一点解析&#xff0c;尽量让基础比较弱的友友也能看懂&#xff0c;希望能给你带来帮助 目录 1. 日期统计 题目描述 解题思路 具体代码 2. 01 串的熵 题目描述 解题思路 具体代码 3. 冶炼金属 题目…

如何编写具有完备性的测试用例 ? 具体思路是什么 ? 全套解决方案打包呈现给你 。

设计测试用例应该算是测试人员最为主要的工作之一 &#xff0c;好的测试用例往往具有覆盖性强 &#xff0c;扩展性高以及复用性好等特点 。该如何设计出好的测试用例 &#xff1f;是我们每一位测试人员需要重点思考的问题 &#xff0c;下面是我对设计测试用例设计的思考 &#…

#RAG|NLP|Jieba|PDF2WORD# pdf转word-换行问题

文档在生成PDF时,文宁都发生了什么。本文讲解了配置对象、resources对象和content对象的作用,以及字体、宇号、坐标、文本摆放等过程。同时,还解释了为什么PDF转word或转文字都是一行一行的以及为什么页眉页脚的问题会加大识别难度。最后提到了文本的编码和PDF中缺少文档结构标…

如何输入手机验证码才能查询?确保本人查询!

易查分的手机验证码功能可以通过预留手机号&#xff0c;让用户查询时输入验证码&#xff0c;确保是本人进行查询。本次就来介绍如何开启【手机验证码功能】。 &#x1f4cc;使用教程 01准备电子表格 在准备表格时&#xff0c;建立查询时&#xff0c;查询条件必须设置两个或者两…

ElementUI 组件:Container 布局容器实例

ElementUI安装与使用指南 Container 布局容器 点击下载learnelementuispringboot项目源码 效果图 项目里el-container-example.vue代码 <script> export default {name: el_container_example,data() {const item {date: 2024-01-31,name: 国龙,address: 上海市某区…

Mac 终端可以使用yarn,但是vscode里面报错segmentation fault

Mac 终端可以使用yarn 但是vscode里面报错segmentation fault 查阅官网https://www.yarnpkg.cn/getting-started/install 在vscode运行corepack enable即可解决该问题

网络异常案例五_SYN被丢弃

问题现象 公司同事使用的时候&#xff0c;反馈系统不稳定&#xff0c;访问的时候&#xff0c;有时候会出现白屏&#xff08;连接超时&#xff09;&#xff0c;或者系统页面点击没有响应&#xff0c;过一会之后刷新系统又可以正常展示了。之前未收到过类似反馈&#xff0c;一直…

20240131在WIN10下配置whisper

20240131在WIN10下配置whisper 2024/1/31 18:25 首先你要有一张NVIDIA的显卡&#xff0c;比如我用的PDD拼多多的二手GTX1080显卡。【并且极其可能是矿卡&#xff01;】800&#xffe5; 2、请正确安装好NVIDIA最新的545版本的驱动程序和CUDA。 2、安装Torch 3、配置whisper http…

2024年数学建模美赛 分析与编程

2024年数学建模美赛 分析与编程 1、本专栏将在2024年美赛题目公布后&#xff0c;进行深入分析&#xff0c;建议收藏&#xff1b; 2、本专栏对2023年赛题&#xff0c;其它题目分析详见专题讨论&#xff1b; 2023年数学建模美赛A题&#xff08;A drought stricken plant communi…

k8s Sidecar filebeat 收集容器中的trace日志和app日志

目录 一、背景 二、设计 三、具体实现 Filebeat配置 K8S SideCar yaml Logstash配置 一、背景 将容器中服务的trace日志和应用日志收集到KAFKA&#xff0c;需要注意的是 trace 日志和app 日志需要存放在同一个KAFKA两个不同的topic中。分别为APP_TOPIC和TRACE_TOPIC 二、…

【笔记】React-Native跟Android交互--简单示例

/** * 使用命令 npx react-nativelatest init DemoRN创建项目 * * "react": "18.2.0", * "react-native": "0.73.2" * * 官网有详细教程&#xff1a;https://reactnative.dev/docs/native-modules-android */ 一、RN invoke androi…