【LeetCode:64. 最小路径和 | 暴力递归=>记忆化搜索=>动态规划 】

news/2024/11/26 9:29:19/

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

    • 🚗 知识回顾
    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 暴力法-DFS
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 记忆化搜索
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
      • ⚡ 动态规划
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚗 知识回顾

大家在学习这道题目之前,可以先去看一下我之前写过的一篇和这个题目类似有类似求解思路的博客,再看这个题目就更容易理解了。
博客的地址放到这里了,可以先去学习一下这到题目。

  • 【LeetCode: 62. 不同路径 | 暴力递归=>记忆化搜索=>动态规划 】

🚩 题目链接

  • 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] <= 100

🌟 求解思路&实现代码&运行结果


⚡ 暴力法-DFS

🥦 求解思路

  1. 这道题目的求解思路比较简单,从左上角0,0位置出发,每次只能向右走或者向下走,到右下角m-1,n-1的路径最小和是多少。
  2. 那么我们直接通过递归-DFS求解即可。

🥦 实现代码

class Solution {public int minPathSum(int[][] grid) {int m=grid.length,n=grid[0].length;return process(0,0,m,n,grid);}public int process(int x,int y,int m,int n,int[][] grid){if(x==m-1&&y==n-1){return grid[x][y];}if(x>=m||y>=n){return Integer.MAX_VALUE;}return Math.min(process(x+1,y,m,n,grid),process(x,y+1,m,n,grid))+grid[x][y];}
}

🥦 运行结果

时间超限了,不要紧张,我们来继续优化它!
在这里插入图片描述


⚡ 记忆化搜索

🥦 求解思路

  1. 因为在递归的过程中,会重复的出现一些多次计算的结果,我们通过开辟一个数组,将结果提前缓存下来,算过的直接返回,避免重复计算,通过空间来去换我们的时间。

🥦 实现代码

class Solution {private int[][] dp;public int minPathSum(int[][] grid) {int m=grid.length,n=grid[0].length;dp=new int[m][n];for(int i=0;i<m;i++) Arrays.fill(dp[i],-1);return process(0,0,m,n,grid);}public int process(int x,int y,int m,int n,int[][] grid){if(x==m-1&&y==n-1){return grid[x][y];}if(x>=m||y>=n){return Integer.MAX_VALUE;}if(dp[x][y]!=-1) return dp[x][y];return dp[x][y]=Math.min(process(x+1,y,m,n,grid),process(x,y+1,m,n,grid))+grid[x][y];}
}

🥦 运行结果

我们发现,通过加一个缓存表,时间复杂度发生了翻天覆地的变化,真是不可思议!
在这里插入图片描述


⚡ 动态规划

🥦 求解思路

  1. 有了递归,有了记忆化搜索,接下来就是动态规划了,直接上手。

🥦 实现代码

class Solution {private int[][] dp;public int minPathSum(int[][] grid) {int m=grid.length,n=grid[0].length;dp=new int[m+1][n+1];dp[m-1][n-1]=grid[m-1][n-1];for(int x=m-2;x>=0;x--){dp[x][n-1]=dp[x+1][n-1]+grid[x][n-1];}for(int y=n-2;y>=0;y--){dp[m-1][y]=dp[m-1][y+1]+grid[m-1][y];}for(int x=m-2;x>=0;x--){for(int y=n-2;y>=0;y--){dp[x][y]=Math.min(dp[x+1][y],dp[x][y+1])+grid[x][y];}}return dp[0][0];}
}

🥦 运行结果

搞定!
在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述


http://www.ppmy.cn/news/55865.html

相关文章

RT-Thread GD32F4xx PWM设备驱动

目录 1、PWM简介2、PWM设备驱动2.1 创建PWM设备2.2 实现PWM设备操作方法2.3 注册PWM设备2.4 PWM配置3、应用测试1、PWM简介 PWM(Pulse Width Modulation,脉冲宽度调制) 是一种对模拟信号电平进行数字编码的方法,通过不同频率的脉冲使用方波的占空比用来对一个具体模拟信号的电…

BM50-两数之和

题目 给出一个整型数组 numbers 和一个目标值 target&#xff0c;请在数组中找出两个加起来等于目标值的数的下标&#xff0c;返回的下标按升序排列。 &#xff08;注&#xff1a;返回的数组下标从1开始算起&#xff0c;保证target一定可以由数组里面2个数字相加得到&#xf…

Java 基础进阶篇(二)—— 面向对象的三大特征之二:继承

文章目录 一、继承概述二、内存运行原理 ★三、继承的特点四、继承后&#xff1a;成员变量和方法的访问特点五、继承后&#xff1a;方法重写六、继承后&#xff1a;子类构造器的特点七、继承后&#xff1a;子类构造器访问父类有参构造器八、this、super 总结 一、继承概述 Jav…

攀高识别预警系统 yolov7

攀高识别预警系统通过yolov7网络模型技术&#xff0c;攀高识别预警系统对人员违规抽烟、打架斗殴、异常倒地、翻越围墙、异常聚集、打电话、区域侵入等行为分析等立即抓拍及时触发告警。YOLOv7 的发展方向与当前主流的实时目标检测器不同&#xff0c;研究团队希望它能够同时支持…

使用pandas、xlrd、openpyxl读取Excel

首先创建一个示例Excel文件example.xlsx&#xff0c;其中包含以下数据&#xff1a; NameAgeGenderAlice28FemaleBob35MaleCharlie42MaleDave29MaleEve31Female 安装 pip install pandas pip install xlrd pip install openpyxl方法一&#xff1a;使用Pandas库 使用Pandas库来…

字节序(附测试本机字节序的代码)

一、字节序测试代码 #include <stdio.h> int main() { unsigned int num 0x12345678; char *p (char*) &num; if (*p 0x12) { printf("This system is big-endian.\n"); } else { printf("This system is little-en…

JVM学习(九):堆

一、堆&#xff08;Heap&#xff09;的概述 一个JVM实例只存在一个堆内存&#xff0c;堆也是Java内存管理的核心区域。 Java堆区在JVM启动的时候即被创建&#xff0c;其空间大小也就确定了。是JVM管理的最大一块内存空间。同时&#xff0c;堆内存的大小是可以调节的。《Java虚拟…

基于DSP+FPGA+ADS1282支持32Bit高精度数据采集方案(二)模拟电路设计

如图 4.1 所示是系统硬件系统的信号框图&#xff0c;数字信号处理板上的主要核心是 两个处理芯片&#xff0c;即 FPGA 和 DSP &#xff0c;其中 FPGA 主要作用是做 DSP 和外围接口的 桥梁及数据预处理&#xff0c; DSP 做为数据解算核心。 FPGA 通过各种的数据总…