算法leetcode|64. 最小路径和(rust重拳出击)


文章目录

  • 64. 最小路径和:
    • 样例 1:
    • 样例 2:
    • 提示:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


64. 最小路径和:

给定一个包含非负整数的 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

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 这道题和62. 不同路径和63. 不同路径 II 有些类似,但是这次是寻找最优解,由于每个位置的数值不一定是多少,所以同样没法使用数学公式直接计算。
  • 那么动态规划又成了此时的优选。
  • 从左上角出发,网格的第一行的每个元素只能从左上角元素开始向右移动到达,网格的第一列的每个元素只能从左上角元素开始向下移动到达,此时的路径是唯一的,因此每个元素对应的最小路径和即为对应的路径上的数字总和。
  • 其他的点只能从上或者从左到达,所以一个点的最优路径,一定经过上面或者左面。从上到下,从左到右开始动态规划,分解成了子问题。到达当前点的最短路径和,就是上面和左面点的最小路径和中的较小值加上当前点的值。
  • 这里一样可以使用滚动数组优化空间。

题解:

rust:

impl Solution {
    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let (rows, cols) = (grid.len(), grid[0].len());
        let mut dp = vec![0; cols];
        dp[0] = grid[0][0];
        (1..cols).for_each(|c| {
            dp[c] = dp[c - 1] + grid[0][c];
        });
        (1..rows).for_each(|r| {
            dp[0] += grid[r][0];
            (1..cols).for_each(|c| {
                dp[c] = dp[c].min(dp[c - 1]) + grid[r][c];
            });
        });
        return dp[cols - 1];
    }
}

go:

func minPathSum(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
	dp := make([]int, cols)
	dp[0] = grid[0][0]
	for c := 1; c < cols; c++ {
		dp[c] = dp[c-1] + grid[0][c]
	}
	for r := 1; r < rows; r++ {
		dp[0] += grid[r][0]
		for c := 1; c < cols; c++ {
			if dp[c-1] < dp[c] {
				dp[c] = dp[c-1] + grid[r][c]
			} else {
				dp[c] += grid[r][c]
			}

		}
	}
	return dp[cols-1]
}

c++:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        const int rows = grid.size(), cols = grid[0].size();
        int dp[cols];
        dp[0] = grid[0][0];
        for (int c = 1; c < cols; ++c) {
            dp[c] = dp[c - 1] + grid[0][c];
        }
        for (int r = 1; r < rows; ++r) {
            dp[0] += grid[r][0];
            for (int c = 1; c < cols; ++c) {
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c];
            }
        }
        return dp[cols - 1];
    }
};

python:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [0] * cols
        for c in range(cols):
            dp[c] = dp[c - 1] + grid[0][c]
        for r in range(1, rows):
            dp[0] += grid[r][0]
            for c in range(1, cols):
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
        return dp[cols - 1]


java:

class Solution {
    public int minPathSum(int[][] grid) {
        final int   rows = grid.length, cols = grid[0].length;
        final int[] dp   = new int[cols];
        dp[0] = grid[0][0];
        for (int c = 1; c < cols; ++c) {
            dp[c] = dp[c - 1] + grid[0][c];
        }
        for (int r = 1; r < rows; ++r) {
            dp[0] += grid[r][0];
            for (int c = 1; c < cols; ++c) {
                dp[c] = Math.min(dp[c], dp[c - 1]) + grid[r][c];
            }
        }
        return dp[cols - 1];
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

windows 安装 mongodb 数据库

软件下载 访问官方的下载地址&#xff1a; https://www.mongodb.com/try/download/community &#xff0c;然后选择对应的版本进行下载 下载好了之后双击进行安装 软件安装 1、点击 next 点击下一步 2、勾选接受协议&#xff0c;点击 next 3、第三页有两个选项&#x…

redisson分布式锁学习

什么是分布式锁? 当有多个线程并发访问同一共享数据时,如果多个线程同时都去修改这个共享数据,且修改操作不是原子操作,就很有可能出现线程安全问题&#xff0c;而产生线程安全问题的根本原因是缺乏对共享数据访问的同步和互斥。 为了解决这个问题&#xff0c;通常我们的做法…

P2P网络NAT穿透原理(打洞方案)

1.关于NAT NAT技术&#xff08;Network Address Translation&#xff0c;网络地址转换&#xff09;是一种把内部网络&#xff08;简称为内网&#xff09;私有IP地址转换为外部网络&#xff08;简称为外网&#xff09;公共IP地址的技术&#xff0c;它使得一定范围内的多台主机只…

SpringBoot超级详解

1.父工程的父工程 在父工程的父工程中的核心依赖&#xff0c;专门用来版本管理的 版本管理。 2.父工程 资源过滤问题&#xff0c;都帮解决了&#xff0c;什么配置文件&#xff0c;都已经配置好了&#xff0c;资源过滤问题是帮助&#xff0c;过滤解决让静态资源文件能够过滤到…

别再分库分表了,来试试它吧

什么是NewSQL传统SQL的问题 升级服务器硬件数据分片NoSQL 的问题 优点缺点NewSQL 特性NewSQL 的主要特性三种SQL的对比TiDB怎么来的TiDB社区版和企业版TIDB核心特性 水平弹性扩展分布式事务支持金融级高可用实时 HTAP云原生的分布式数据库高度兼容 MySQLOLTP&OLAP&#xff…

openssl/bn.h: No such file or directory

报错截图 解决方法 ubuntu apt install libssl-dev -y centos yum install openssl-devel -y

第六章 支持向量机

文章目录 支持向量机间隔和支持向量对偶问题问题推导SMO 核函数实验 支持向量机 ⽀持向量机&#xff08;Support Vector Machines&#xff0c;SVM&#xff09; 优点&#xff1a;泛化错误率低&#xff0c;计算开销不⼤&#xff0c;结果易解释。缺点&#xff1a;对参数调节和核…

Python 教程之标准库概览

概要 Python 标准库非常庞大&#xff0c;所提供的组件涉及范围十分广泛&#xff0c;使用标准库我们可以让您轻松地完成各种任务。 以下是一些 Python3 标准库中的模块&#xff1a; 「os 模块」 os 模块提供了许多与操作系统交互的函数&#xff0c;例如创建、移动和删除文件和…

CLIP-GCD: Simple Language Guided Generalized Category Discovery(论文翻译)

CLIP-GCD: Simple Language Guided Generalized Category Discovery 摘要1 介绍2 相关工作2.1 NCD2.2 无监督聚类2.3 自监督和多模态预训练 3 方法3.1 GCD 问题设置3.2 我们的方法3.2.1 使用CLIP 在GCD 4 实验4.1 模型架构细节4.2 数据集和评估4.3 和最先进水平比较4.4 分析4.5…

Linux下 Docker容器引擎基础(1)

简述&#xff1a; Docker的容器技术可以在一台主机上轻松为任何应用创建一个轻量级的、可移植的、自给自足的容器。通过这种容器打包应用程序&#xff0c;意味着简化了重新部署、调试这些琐碎的重复工作&#xff0c;极大的提高了工作效率。例如&#xff1a;项目从腾讯云迁移阿…

尚硅谷大数据项目《在线教育之采集系统》笔记002

视频地址&#xff1a;尚硅谷大数据项目《在线教育之采集系统》_哔哩哔哩_bilibili 目录 P032 P033 P033 P034 P035 P036 P032 P033 # 1、定义组件&#xff0c;为各组件命名 a1.sources r1 a1.channels c1 a1.sinks - k1# 2、配置sources&#xff0c;描述source a1.sour…

ALLEGRO之Route菜单

本文主要介绍了ALLEGRO的Route菜单。 &#xff08;1&#xff09;Connect&#xff1a;走线&#xff1b; &#xff08;2&#xff09;Slide&#xff1a;推挤&#xff1b; &#xff08;3&#xff09;Timing Vision&#xff1a;等长设计时使用&#xff1f;暂不清楚&#xff1b; &…

oracle,获取每日24*60,所有分钟数

前言&#xff1a; 为规范用户的时间录入&#xff0c;因此我们采用下拉的方式&#xff0c;让用户选择需要的时间&#xff0c;因此我们需要将一天24小时的时间拆分为类似00:00,00:01...23:00,23:01,23:59。因此我们需要生成24*601440行的下拉复选值。具体效果如下图所示。 思路 1…

C语言字串函数、内存函数介绍以及模拟实现

目录 前言 本期内容介绍&#xff1a; 一、字符串函数 strlen介绍 strlen 模拟实现&#xff08;三种方式&#xff09; 方法一&#xff1a;计数器法 方法二&#xff1a;递归法&#xff08;不创建临时变量法&#xff09; 方法三&#xff1a;指针-指针 strcpy介绍 strcpy模…

SSIS对SQL Server向Mysql数据转发表数据 (完结)

1、对于根据主键进行更新和插入新的数据&#xff0c;根据前面的文章&#xff0c;对于组件已经很熟悉了&#xff0c;我们直接加入一个 查找 组件 &#xff0c;如下所示 2、右键点击"查找"&#xff0c;然后“编辑” &#xff0c;选择“连接”,选中我们的目标连接器&…

Vue2 第七节 Vue监测数据更新原理

&#xff08;1&#xff09;Vue会监视data中所有层次的数据 &#xff08;2&#xff09;如何监测对象中的数据 通过setter实现监视&#xff0c;且要在new Vue时传入要监测的数据对象中后追加的属性&#xff0c;Vue默认不做响应式处理如果要给后添加的属性做响应式&#xff0c;使…

Docker私有仓库

Docker私有仓库 Docker官方的Docker hub&#xff08;https://hub.docker.com&#xff09;是一个用于管理公共镜像的仓库&#xff0c;我们可以从上面拉取镜像到本地&#xff0c;也可以把我们自己的镜像推送上去。但是&#xff0c;有时候我们的服务器无法访问互联网&#xff0c;…

初阶数据结构——二叉树题目

文章目录 一、单值二叉树二、检查两颗树是否相同三、另一棵树的子树四、二叉树的前序遍历五、对称二叉树 一、单值二叉树 单值二叉树 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时&#xff0c;才返回 true&#xff…

Docker学习笔记,包含docker安装、常用命令、dockerfile、docker-compose等等

&#x1f600;&#x1f600;&#x1f600;创作不易&#xff0c;各位看官点赞收藏. 文章目录 Docker 学习笔记1、容器2、Docker 安装3、Docker 常用命令4、Docker 镜像5、自定义镜像5.1、镜像推送到阿里云5.2、镜像私有库 6、数据卷7、Docker 软件安装8、Docker File8.1、常见保…

基于python+Xception算法模型实现一个图像分类识别系统

一、目录 Xception介绍数据集处理模型训练模型评估项目扩展 二、Xception介绍 在计算机视觉领域&#xff0c;图像识别是一个非常重要的任务&#xff0c;其应用涵盖了人脸识别、物体检测、场景理解等众多领域。随着深度学习技术的发展&#xff0c;深度卷积神经网络&#xff0…